Thickness and colorability of geometric graphs

DOI10.1016/J.COMGEO.2016.03.003MaRDI QIDQ679741zbMATH OpenOpenAlexFDO

Authors Stephane Durocher, Ellen Gethner, Debajyoti Mondal

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) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Thickness and colorability of geometric graphs
• Geometric Thickness of Complete Graphs
• Bounded-degree graphs have arbitrarily large geometric thickness
• On graph thickness, geometric thickness, and separator theorems
• The geometric thickness of low degree graphs

Cites work

• scientific article; zbMATH DE number 2145231 (Why is no real title available?)
• scientific article; zbMATH DE number 3195968 (Why is no real title available?)
• scientific article; zbMATH DE number 3199421 (Why is no real title available?)
• 25 pretty graph colouring problems
• Bounded-degree graphs have arbitrarily large geometric thickness
• Determining the thickness of graphs is NP-hard
• Enumerating order types for small point sets with applications
• Every planar map is four colorable. I: Discharging
• Geometric Thickness of Complete Graphs
• Graph Drawing
• Graph treewidth and geometric thickness parameters
• Maximizing the degree of (geometric) thickness-\(t\) regular graphs
• On graph thickness, geometric thickness, and separator theorems
• On representations of some thickness-two graphs
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Simultaneous Embedding of Planar Graphs with Few Bends
• THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
• The complexity of the empire colouring problem
• The geometric thickness of low degree graphs
• The thickness of graphs: A survey
• Thickness and coarseness of graphs
• Thickness and colorability of geometric graphs

Cited in

(15)

• On the geometric thickness of 2-degenerate graphs
• The thickness and chromatic number of \(r\)-inflated graphs
• scientific article; zbMATH DE number 2145231 (Why is no real title available?)
• Geometric thickness in a grid
• On graph thickness, geometric thickness, and separator theorems
• Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete
• Geometric Thickness of Complete Graphs
• On the complexity of some geometric problems with fixed parameters
• Utilizing graph thickness heuristics on the Earth-Moon problem
• The geometric thickness of low degree graphs
• Thickness and colorability of geometric graphs
• A genetic algorithm for determining the thickness of a graph
• On representations of some thickness-two graphs
• 3-coloring arrangements of line segments with 4 slopes is hard
• Relating graph thickness to planar layers and bend complexity

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

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