Everything about Pathwidth
Representation of a graph as a path graph "thickened" by some amount
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: PathwidthA 5-minute orientation
- Skim a recent paper: Approximating Pathwidth for Graphs of Small TreewidthInfluential work since 2022
- Pick up a classic book: A relative approximation algorithm for computing the path-width of outerplanar graphsThe most-reprinted book on the subject
- Read the landmark paper: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of GraphsCited 218 times
- Go sideways: TreewidthA closely related topic
- Go sideways: Tree decompositionA closely related topic
📖 Definitions
Noun A measure of a path decomposition of a graph.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
The Pathwidth and Treewidth of Cographs
Treewidth and Pathwidth of Permutation Graphs
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
On the pathwidth of chordal graphs
Pathwidth of cubic graphs and exact algorithms
Herding in groundfish and effective pathwidth of trawls
🆕 Influential since 2022
📚 Books worth reading
- 📕A relative approximation algorithm for computing the path-width of outerplanar graphsXudong Yan · 1989
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest…
- Tree decomposition In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain…
- Tree-depth In graph theory, the tree-depth of a connected undirected graph G {\displaystyle G} is a numerical invariant of G {\displaystyle G} , the minimum height…
- Branch-decomposition In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree…
- Courcelle's theorem In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs…
- Partial k-tree In graph theory, a partial k-tree is a type of graph, defined either as a subgraph of a k-tree or as a graph with treewidth at most k. Many NP-hard combinatoria…
- Clique-width In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth…
- Chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not…