On graph thickness, geometric thickness, and separator theorems

DOI10.1016/j.comgeo.2010.09.005zbMath1205.05161MaRDI QIDQ621923

Christian A. Duncan

Publication date: 31 January 2011

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.09.005

zbMATH Keywords

arboricity; outerthickness; geometric thickness; graph thickness; planar separators

Mathematics Subject Classification ID

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On simultaneous planar graph embeddings
• On the Hadwiger's conjecture for graph products
• Multilayer grid embeddings for VLSI
• Two trees which are self-intersecting when drawn simultaneously
• The linear arboricity of graphs
• The book thickness of a graph
• On the thickness of graphs of given degree
• A partial k-arboretum of graphs with bounded treewidth
• The thickness of graphs: A survey
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Graph treewidth and geometric thickness parameters
• Thickness and coarseness of graphs
• Bounded-degree graphs have arbitrarily large geometric thickness
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• A Separator Theorem for Planar Graphs
• Covering and packing in graphs IV: Linear arboricity
• A Separator Theorem for Nonplanar Graphs
• Planar Separators
• Graphs with E Edges Have Pagenumber O(√E)
• Geometric Thickness of Complete Graphs
• The geometric thickness of low degree graphs
• The Non-Biplanar Character of the Complete 9-Graph
• Every planar graph with nine points has a nonplanar complement
• Decomposition of Finite Graphs Into Forests
• Embedding planar graphs at fixed vertex locations