Thickness and colorability of geometric graphs

DOI10.1016/j.comgeo.2016.03.003zbMath1384.05086OpenAlexW2302259827MaRDI QIDQ679741

Debajyoti Mondal, Ellen Gethner, Stephane Durocher

Publication date: 19 January 2018

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

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

zbMATH Keywords

coloringcomplete graphgeometric thickness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)

Related Items (3)

Relating Graph Thickness to Planar Layers and Bend Complexity ⋮ Planar projections of graphs ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of the empire colouring problem
• On graph thickness, geometric thickness, and separator theorems
• Every planar map is four colorable. I: Discharging
• The thickness of graphs: A survey
• Enumerating order types for small point sets with applications
• On representations of some thickness-two graphs
• Graph treewidth and geometric thickness parameters
• Thickness and coarseness of graphs
• Bounded-degree graphs have arbitrarily large geometric thickness
• Thickness and Colorability of Geometric Graphs
• Maximizing the Degree of (Geometric) Thickness-t Regular Graphs
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Determining the thickness of graphs is NP-hard
• THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
• Geometric Thickness of Complete Graphs
• Simultaneous Embedding of Planar Graphs with Few Bends
• The geometric thickness of low degree graphs
• Graph Drawing
• 25 pretty graph colouring problems

This page was built for publication: Thickness and colorability of geometric graphs