Drawing some 4-regular planar graphs with integer edge lengths
Timothy Sun · 2013
A classic result of F ary states that every planar graph can be drawn in the plane without crossings using only straight line segments. Harborth et al. conjecture that every planar graph has such a drawing where every edge length is integral. Biedl proves that every planar graph of maximum degree 4 that is not 4-regular has such a straight-line embedding, but the techniques are insucient for 4-regular graphs. We further develop the rigidity-theoretic methods of the author and examine an incomplete construction of Kemnitz and Harborth to exhibit integral drawings of families of 4-regular graphs.