David Eppstein (University of California, Irvine): Circle packings, hyperbolic Voronoi diagrams, Lombardi drawings, and soap bubbles

We show how to use three-dimensional hyperbolic geometry to form a type of Voronoi diagram for a collection of disjoint circles in the plane that is invariant under Möbius transformations. By applying this method to systems of circles formed from the Koebe?Thurston?Andreev circle packing theorem, together with decompositions of graphs into their 2-connected and 3-connected components, we show that all planar graphs of degree at most three have planar Lombardi drawings (graph drawings in which each edge is a circular arc and in which the edges meet at equal angles at each vertex). We also find planar Lombardi drawings for 4-regular planar graphs with sufficient connectivity, but we exhibit a 4-regular planar graph that does not have a planar Lombardi drawing. Finally, we use the same construction to investigate the graph-theoretic properties of soap bubbles.