#
Planar Lombardi Drawings for Subcubic Graphs

##
David Eppstein

We prove that every planar graph with maximum degree
three has a planar drawing in which the edges are drawn as circular
arcs that meet at equal angles around every vertex. Our construction
is based on the Koebeâ€“Andreevâ€“Thurston circle packing theorem, and
uses a novel type of Voronoi diagram for circle packings that is
invariant
under Mobius transformations, defined using three-dimensional
hyperbolic
geometry. We also use circle packing to construct planar Lombardi
drawings of a special class of 4-regular planar graphs, the medial
graphs
of polyhedral graphs, and we show that not every 4-regular planar
graph
has a planar Lombardi drawing. We have implemented our algorithm for
3-connected planar cubic graphs.