  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.
