The Effect of Planarization on Width

DOI10.1007/978-3-319-73915-1_43zbMath1499.05428arXiv1708.05155MaRDI QIDQ4625143

David Eppstein

Publication date: 20 February 2019

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C07: Vertex degrees

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

The Effect of Planarization on Width, Unnamed Item, Lower bounds for protrusion replacement by counting equivalence classes

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
• Which crossing number is it anyway?
• Lower bounds for protrusion replacement by counting equivalence classes
• Square roots of minor closed graph classes
• On maximal planarization of nonplanar graphs
• An analysis of heuristics for graph planarization
• The Effect of Planarization on Width
• Planar Induced Subgraphs of Sparse Graphs
• On the Relationship Between Clique-Width and Treewidth
• The crossing number of K5,n
• On the undecidability of finite planar graphs
• On a problem of P. Turan concerning graphs