The effect of planarization on width

DOI10.7155/JGAA.00468MaRDI QIDQ4961755zbMATH OpenOpenAlexWikidataFDO

Authors David Eppstein

Publication date 25 October 2018

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• The effect of planarization on width
• On the path-width of planar graphs
• Crossing Numbers and Cutwidths
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Planar decompositions and the crossing number of graphs with an excluded minor

Cites work

• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 2084266 (Why is no real title available?)
• A better bound for the pair-crossing number
• A separator theorem for string graphs and its applications
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• An analysis of heuristics for graph planarization
• Applications of a new separator theorem for string graphs
• Call routing and the ratcatcher
• Graph minors. II. Algorithmic aspects of tree-width
• Graphs with small bandwidth and cutwidth
• Improved upper bounds on the crossing number
• Lower bounds for protrusion replacement by counting equivalence classes
• Near-optimal separators in string graphs
• On a problem of P. Turan concerning graphs
• On graph crossing number and edge planarization
• On maximal planarization of nonplanar graphs
• On the Relationship Between Clique-Width and Treewidth
• On the undecidability of finite planar graphs
• Planar decompositions and the crossing number of graphs with an excluded minor
• Planar induced subgraphs of sparse graphs
• Sparsity. Graphs, structures, and algorithms
• Square roots of minor closed graph classes
• The crossing number of K5,n
• The vertex separation number of a graph equals its path-width
• Topologically sweeping an arrangement

Cited in

(7)

• Incremental and Decremental Maintenance of Planar Width
• An analysis of the parameterized complexity of periodic timetabling
• The effect of planarization on width
• The graphs of stably matchable pairs
• Lower bounds for protrusion replacement by counting equivalence classes
• On quasi-planar graphs: clique-width and logical description
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth

This page was built for publication: The effect of planarization on width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4961755)