Results 51 to 60 of about 609 (128)
On tree decompositions whose trees are minors
Journal of Graph Theory, Volume 106, Issue 2, Page 296-306, June 2024.Abstract In 2019, Dvořák asked whether every connected graph G $G$ has a tree decomposition ( T , B ) $(T,{\rm{ {\mathcal B} }})$ so that T $T$ is a subgraph of G $G$ and the width of ( T , B ) $(T,{\rm{ {\mathcal B} }})$ is bounded by a function of the treewidth of G $G$.
Pablo Blanco +5 more
wiley +1 more source
On the pathwidth of chordal graphs
Discrete Applied Mathematics, 1993 AbstractIn this paper we first show that the pathwidth problem for chordal graphs is NP-hard.Then we give polynomial algorithms for subclasses. One of those classes are the k-starlike graphs – a generalization of split graphs. The other class are the primitive starlike graphs – a class of graphs where the intersection behavior of maximal cliques is ...
openaire +2 more sources
The product structure of squaregraphs
Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham +3 more
wiley +1 more source
Two Results on Layered Pathwidth and Linear Layouts [PDF]
arXiv, 2020 Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph $G$, the stack number of $G$ is at most four times the layered pathwidth of $G$.
arxiv
IET Intelligent Transport Systems, Volume 18, Issue 1, Page 186-202, January 2024.In the context of automated driving, the connected and automated vehicles (CAVs) technology unlock the energy saving potential. This paper develops an LSTM‐based deep learning framework for eco‐driving adaptive identification on Intelligent vehicle multivariate time series data.
Lixin Yan +4 more
wiley +1 more source
Seymour’s Conjecture on 2-Connected Graphs of Large Pathwidth [PDF]
Combinatorica, 2020 We prove the conjecture of Seymour (1993) that for every apex-forest $H_1$ and outerplanar graph $H_2$ there is an integer $p$ such that every 2-connected graph of pathwidth at least $p$ contains $H_1$ or $H_2$ as a minor. An independent proof was recently obtained by Dang and Thomas.
Huynh T., Joret G., Micek P., Wood D. R.
openaire +4 more sources
Induced subgraphs and path decompositions [PDF]
arXiv, 2022 A graph $H$ is an induced subgraph of a graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by deleting vertices. Recently, there has been significant interest in understanding the unavoidable induced subgraphs for graphs of large treewidth.
arxiv
On the complexity of embedding in graph products [PDF]
arXiv, 2023 Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph $G$ in a host graph that is the strong product of a path $P$ with a graph $H$ that satisfies some properties, such as having small treewidth, pathwidth or ...
arxiv
On the Pathwidth of Planar Graphs [PDF]
, 2006 Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by Coudert, Huc and Sereni in [4]). By the results of Boedlander and Fomin [2] this holds for every outerplanar graph and actually is tight by Coudert, Huc and
Amini, Omid +2 more
openaire +3 more sources
Track Layouts, Layered Path Decompositions, and Leveled Planarity [PDF]
Algorithmica 81 (4): 1561-1583, 2019, 2015 We investigate two types of graph layouts, track layouts and layered path decompositions, and the relations between their associated parameters track-number and layered pathwidth. We use these two types of layouts to characterize leveled planar graphs, which are the graphs with planar leveled drawings with no dummy vertices.
arxiv +1 more source