CS 269S, Fall 2012: Theory Seminar
Bren Hall, Room 1423, 1pm
October 19, 2012:

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.