6 papers · 1 filter
Optimal Tree-Decompositions with Bags of Bounded Treewidth
Kevin Hendrey, David R. Wood
We prove that several natural graph classes have tree-decompositions with minimum width such that each bag has bounded treewidth. For example, every planar graph has a tree-decompo…
Embedding Graphs of Simple Treewidth into Sparse Products
Kevin Hendrey, David R. Wood, Jung Hon Yip
We study embeddings of graphs with bounded treewidth or bounded simple treewidth into the undirected graph underlying the directed product of two directed graphs. If the factors ha…
On universal graphs for trees and treewidth graphs
Neel Kaul, David R. Wood
Let be the minimum number of edges in a graph that contains every -vertex tree as a subgraph. Chung and Graham [J. London Math. Soc. 1983] claim to prove that $s(n)\leqsl…
Structure of -Matching-Planar Graphs
Kevin Hendrey, Nikolai Karol, David R. Wood
For , we define a simple topological graph (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…
Polynomial Bounds in the Apex Minor Theorem
Kevin Hendrey, David R. Wood
A graph is "apex" if is planar for some vertex . Eppstein [Algorithmica, 2000] showed that for a minor-closed class , the graphs in …
Short Paths in the Planar Graph Product Structure Theorem
Kevin Hendrey, David R. Wood
The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph is contained in for some planar graph wi…