Thickness and colorability of geometric graphs
type: Item
instance of: scholarly article
title: Thickness and colorability of geometric graphs
zbMATH Open document ID: 1384.05086
author: Stephane Durocher
author: Ellen Gethner
author: Debajyoti Mondal
published in: Computational Geometry
publication date: 2018-01-19T00:00:00Z
review text: The authors consider the thickness and geometric thickness of graphs. They give an example of a graph with thickness equal to 2 and geometric thickness equal to 3. They prove that the problem of recognizing geometric thickness is NP-hard even for graphs with geometric thickness equal to 2. Moreover, they give the proof of NP-hardness of \((4t-1)\)-coloring graphs with geometric thickness \(t\). The paper improves known results in this topic.
reviewed by: Hanna Furmańczyk
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6827953
zbMATH Keywords: complete graph
zbMATH Keywords: geometric thickness
zbMATH Keywords: coloring
MaRDI profile type: Publication
full work available at URL: j.comgeo.2016.03.003
OpenAlex ID: W2302259827
cites work: Thickness and Colorability of Geometric Graphs
cites work: Q5735733
cites work: THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
cites work: Q5732335
cites work: Geometric Thickness of Complete Graphs
cites work: Determining the thickness of graphs is NP-hard
cites work: The thickness of graphs: A survey
cites work: Q4657580
cites work: On representations of some thickness-two graphs
cites work: Bounded-degree graphs have arbitrarily large geometric thickness
cites work: The geometric thickness of low degree graphs
cites work: Graph treewidth and geometric thickness parameters
cites work: On graph thickness, geometric thickness, and separator theorems
cites work: Thickness and coarseness of graphs
cites work: Graph Drawing
cites work: Every planar map is four colorable. I: Discharging
cites work: 25 pretty graph colouring problems
cites work: The complexity of the empire colouring problem
cites work: Enumerating order types for small point sets with applications
cites work: Simultaneous Embedding of Planar Graphs with Few Bends
cites work: SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
cites work: Maximizing the Degree of (Geometric) Thickness-t Regular Graphs
DOI: 10.1016/J.COMGEO.2016.03.003
description: scientific article; zbMATH DE number 6827953