Thickness and colorability of geometric graphs
DOI10.1016/J.COMGEO.2016.03.003zbMATH Open1384.05086OpenAlexW2302259827MaRDI QIDQ679741FDOQ679741
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
Recommendations
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)
Cites Work
- Every planar map is four colorable. I: Discharging
- 25 pretty graph colouring problems
- Graph Drawing
- SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
- Bounded-degree graphs have arbitrarily large geometric thickness
- Enumerating order types for small point sets with applications
- Simultaneous Embedding of Planar Graphs with Few Bends
- Graph treewidth and geometric thickness parameters
- The thickness of graphs: A survey
- The complexity of the empire colouring problem
- Title not available (Why is that?)
- Thickness and coarseness of graphs
- Thickness and colorability of geometric graphs
- Geometric Thickness of Complete Graphs
- Title not available (Why is that?)
- The geometric thickness of low degree graphs
- Title not available (Why is that?)
- On graph thickness, geometric thickness, and separator theorems
- On representations of some thickness-two graphs
- Maximizing the degree of (geometric) thickness-\(t\) regular graphs
- Determining the thickness of graphs is NP-hard
- THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
Cited In (16)
- A genetic algorithm for determining the thickness of a graph
- On representations of some thickness-two graphs
- Geometric Thickness of Complete Graphs
- 3-coloring arrangements of line segments with 4 slopes is hard
- Title not available (Why is that?)
- Relating graph thickness to planar layers and bend complexity
- On the geometric thickness of 2-degenerate graphs
- The geometric thickness of low degree graphs
- On graph thickness, geometric thickness, and separator theorems
- Thickness and colorability of geometric graphs
- On the complexity of some geometric problems with fixed parameters
- Planar projections of graphs
- The thickness and chromatic number of \(r\)-inflated graphs
- Utilizing graph thickness heuristics on the Earth-Moon problem
- Geometric thickness in a grid
- Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete
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)
