The Effect of Planarization on Width

DOI10.7155/jgaa.00468zbMath1398.05141OpenAlexW3106486826WikidataQ129833597 ScholiaQ129833597MaRDI QIDQ4961755

David Eppstein

Publication date: 25 October 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00468

zbMATH Keywords

treewidthpathwidthbranchwidthgraphs of bounded degree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

An analysis of the parameterized complexity of periodic timetabling ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ The graphs of stably matchable pairs ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Graphs with small bandwidth and cutwidth
• Topologically sweeping an arrangement
• The vertex separation number of a graph equals its path-width
• Call routing and the ratcatcher
• Planar decompositions and the crossing number of graphs with an excluded minor
• Square roots of minor closed graph classes
• A Better Bound for the Pair-Crossing Number
• A Separator Theorem for String Graphs and its Applications
• Improved upper bounds on the crossing number
• Graph minors. II. Algorithmic aspects of tree-width
• On maximal planarization of nonplanar graphs
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• An analysis of heuristics for graph planarization
• Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
• Planar Induced Subgraphs of Sparse Graphs
• On the Relationship Between Clique-Width and Treewidth
• Applications of a New Separator Theorem for String Graphs
• Near-Optimal Separators in String Graphs
• The crossing number of K5,n
• On the undecidability of finite planar graphs
• On a problem of P. Turan concerning graphs

This page was built for publication: The Effect of Planarization on Width