Thickness and colorability of geometric graphs (Q679741): Difference between revisions

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.