The Geometric Thickness of Low Degree Graphs
<|reference_start|>The Geometric Thickness of Low Degree Graphs: We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design.<|reference_end|>
@article{duncan2003the,
    title={The Geometric Thickness of Low Degree Graphs},
    author={Christian A. Duncan (University of Miami), David Eppstein (University
  of California, Irvine), Stephen G. Kobourov (University of Arizona)},
    journal={arXiv preprint arXiv:cs/0312056},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0312056},
    primaryClass={cs.CG cs.DM}
}