A lower bound on the tree-width of graphs with irrelevant vertices

DOI10.1016/j.jctb.2018.12.008zbMath1416.05155arXiv1901.04325OpenAlexW2906524658WikidataQ61821297 ScholiaQ61821297MaRDI QIDQ2312606

Philipp Klaus Krause, Isolde Adler

Publication date: 17 July 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.04325

zbMATH Keywords

planar graphtree-widthdisjoint paths problemirrelevant vertexunique linkagevital linkage

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Related Items

From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm

Cites Work

• Unnamed Item
• Irrelevant vertices for the planar disjoint paths problem
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Explicit bounds for graph minors
• Graph minors. XXI. graphs with unique linkages
• Graph minors. XIII: The disjoint paths problem
• Untangling two systems of noncrossing curves
• Tight Bounds for Linkages in Planar Graphs
• On the Computational Complexity of Combinatorial Problems
• Congruent Graphs and the Connectivity of Graphs