Results 11 to 20 of about 609 (128)
From Pathwidth to Connected Pathwidth [PDF]
SIAM J. Discrete Mathematics 26 (2012) 1709-1732, 2010 It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\pw(G)+1$, where $\pw(G)$ is the pathwidth of $G$. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$,
Dariusz Dereniowski
arxiv +12 more sources
Bandwidth and pathwidth of three-dimensional grids [PDF]
arXiv, 2011 We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case.
Yota Otachi, Ryohei Suda
arxiv +5 more sources
Kernel Bounds for Structural Parameterizations of Pathwidth [PDF]
Lecture Notes in Computer Science 7357 (2012) 352-363, 2012 Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth with respect to other, structural, parameters. Our main result is that, unless NP is in coNP/poly,
Hans L. Bodlaender +2 more
arxiv +8 more sources
Crossing Number for Graphs With Bounded Pathwidth [PDF]
arXiv, 2016 The crossing number is the smallest number of pairwise edge-crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios.
Thérèse Biedl +3 more
arxiv +8 more sources
$b$-Coloring Parameterized by Pathwidth is XNLP-complete [PDF]
arXiv, 2022 We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the parameterized complexity of $b$-Coloring parameterized
Lars Jaffke +2 more
arxiv +3 more sources
Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs
Discrete Mathematics, 2002 AbstractIn this paper, it is shown that the maximum pagenumber of the graphs with pathwidth k is k and that the maximum pagenumber of the graphs with strong pathwidth k is in between ⌈3(k−1)/2⌉ and 3⌈k/2⌉.
Mitsunori Togasaki, Koichi Yamazaki
openalex +3 more sources
Triangulating planar graphs while keeping the pathwidth small [PDF]
arXiv, 2015 Any simple planar graph can be triangulated, i.e., we can add edges to it, without adding multi-edges, such that the result is planar and all faces are triangles. In this paper, we study the problem of triangulating a planar graph without increasing the pathwidth by much. We show that if a planar graph has pathwidth $k$, then we can triangulate it so
Thérèse Biedl
arxiv +3 more sources
Cycle decompositions of pathwidth‐6 graphs [PDF]
Journal of Graph Theory, Volume 94, Issue 2, Page 224-251, June 2020., 2020 Abstract Hajós' conjecture asserts that a simple Eulerian graph on n vertices can be decomposed into at most ⌊ ( n − 1 ) / 2 ⌋ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions.
Elke Fuchs +2 more
wiley +5 more sources
Minor-closed graph classes with bounded layered pathwidth [PDF]
SIAM J. Discrete Math., 34(3), 1693-1709, 2020, 2018 We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.
Vida Dujmović +4 more
arxiv +3 more sources
Treewidth and Pathwidth of Permutation Graphs [PDF]
SIAM Journal on Discrete Mathematics, 1995 In this paper we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few non-trivial graph classes for which at the moment, treewidth is known to be computable in polynomial ...
Hans L. Bodlaender +2 more
+8 more sources