Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 467 papers for “Pathwidth”

Treewidth and Pathwidth of Permutation Graphs

Hans L. Bodlaender, Ton Kloks, Dieter Kratsch · 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 nontrivial graph classes for which, at the moment, treewidth is known to be computable in polynomial time. Our algorithm, which decides whether the treewidth (pathwidth) is at most some given integer k, can be implemented to run in $O( nk )$ time when the matching diagram is given. We show that this algorithm can easily be adapted to compute the pathwidth of a permutation graph in $O( nk )$ time, where k is the pathwidth.

Cited by 111

Matroid Pathwidth and Code Trellis Complexity

Navin Kashyap · SIAM Journal on Discrete Mathematics · 2008

We relate the notion of matroid pathwidth to the minimum trellis state-complexity (which we term trellis-width) of a linear code and to the pathwidth of a graph. By reducing from the problem of computing the pathwidth of a graph, we show that the problem of determining the pathwidth of a representable matroid is NP-hard. Consequently, the problem of computing the trellis-width of a linear code is also NP-hard. For a finite field $\F$, we also consider the class of $\F$-representable matroids of pathwidth at most w, and correspondingly, the family of linear codes over $\F$ with trellis-width at most w. These are easily seen to be minor-closed. Since these matroids (and codes) have branchwidth at most w, a result of Geelen and Whittle shows that such matroids (and the corresponding codes) are characterized by finitely many excluded minors. We provide the complete list of excluded minors for $w=1$ and give a partial list for $w=2$.

Cited by 32

ON SELF DUALITY OF PATHWIDTH 43

Graph Embeddings, Fedor V. Fomin, Dimitrios M. Thilikos · 2005

DOI 10.1002/jgt.20219 Abstract: Let G be a 3-connected planar graph and G ∗ be its dual. We show that the pathwidth of G ∗ is at most 6 times the pathwidth of G. We prove this result by relating the pathwidth of a graph with the cut-width of its medial graph and we extend it to bounded genus embeddings. We also show that there exist 3-connected planar graphs such that the pathwidth of such a graph is at least 1.5 times the pathwidth of its dual. © 2007 Wiley

Cited by 0

Circumference and Pathwidth of Highly Connected Graphs

Emily A. Marshall, David R. Wood · Journal of Graph Theory · 2014

Abstract Birmele [ J Graph Theory 2003] proved that every graph with circumference t has treewidth at most . Under the additional assumption of 2‐connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem was extended by Birmele et al. [ Combinatorica 2007] who showed that every graph without k disjoint cycles of length at least t has treewidth . Our main result states that, under the additional assumption of ‐connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth . Moreover, examples show that ‐connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of k and graphs H does every k ‐connected H ‐minor‐free graph have bounded pathwidth? We discuss this question and provide a few observations.

Cited by 3Open access

TREEWIDTH and PATHWIDTH parameterized by vertex cover

Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca et al. · arXiv (Cornell University) · 2013

After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3^k) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover.

Cited by 1Open access

Pathwidth of 2-Layer k-Planar Graphs

Yuto Okada · arXiv (Cornell University) · 2025

A bipartite graph G = (X ∪ Y, E) is a 2-layer k-planar graph if it admits a drawing on the plane such that the vertices in X and Y are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most k crossings. Angelini, Da Lozzo, Förster, and Schneck [GD 2020; Comput. J., 2024] showed that every 2-layer k-planar graph has pathwidth at most k + 1. In this paper, we show that this bound is sharp by giving a 2-layer k-planar graph with pathwidth k + 1 for every k ≥ 0. This improves their lower bound of (k + 3) / 2.

Cited by 0Open access