Balanced Circle Packings for Planar Graphs - Graph Drawing - page 134

path in one of the trees leads directly to a long path in the graph and large 3-connected
components have long paths by results of Chen and Yu [6].
Because each 3-connected component must have bounded size, the circle packing
theorem gives it a balanced circle packing. Next, we construct a contact representation
for a supergraph of the given graph, by using Mobius transformations to gluetogether
these packings. The virtual edge representing two adjacent components in an SPQR tree
should be represented by a pair of tangent circles shared by the packingsforthetwo
components; two tangent circles may be shared by an unbounded number of compo-
nents. We find a family of Mobius transformations that pack all these components into
the space surrounding the two shared tangent circles, so that the components are oth-
erwise disjoint from each other, and each is distorted by a polynomial factor. By using
this method to combine adjacent nodes of the block-cutandSPQR trees, we obtain a
balanced circle packing for the whole graph in which each component is transformed a
constant number of times with polynomial distortion per transformation. However, we
may have additional unwanted tangencies between circles, coming from virtual edges
in an SPQR tree node that do not correspond to graph edges.
The final part of our proof of Theorem 5 shows how to perturb these glued-together
packings, in a controlled way, to eliminate the contacts between pairs of vertices that
are connected by virtual edges but not by edges of the input graph while still allowing
the M obius gluing to work correctly. The existence of a M obius transformation from
one pair of circles to another is controlled by an invariant of pairs of circles called their
inversivedistance that equals 1 for tangent circles, is less than 1 for crossing circles, and
is greater than 1 for disjoint circles. The theory of inversive distance circle packingsis
not as well-developed as the theory of tangent circle packings, butatheoremofLuo[17]
implies that, for a maximal planar graph with specified positions for the centers of the
three circles representing the outer face of the graph and specified inversive distances
on each edgeofthegraph, a circle packing of this type is unique when it exists. By
combining this fact with Brouwer's theorem of invariance of domain, we show that
for any fixed maximal planar graph (and fixed three outer circle centers) the space of
feasible assignments of inversive distances to edges of the graph forms an open set.
Therefore, for all sufficiently small ʵ> 0, there exist packings for which all virtual-
but-not-actual edges have inversive distance 1+ ʵ and all actual edges have inversive
distance 1. Choosing ʵ to be inverse-polynomially small allows the same gluing method
to complete the construction and the proof.
5Conluion
We s tudied balanced circle packings for planar graphs, showing that several rich classes
of graphs have balanced circle packings. One interesting open problem is whether or
not every outerplanar graph has a balanced circle packing representation. While we
identified several subclasses of outerplanar graphs that admit such representations, the
question remains open for general outerplanar graphs.
Acknowledgments. This work is supported in part by the National Science Foundation
under grants CCF-1228639, CCF-1115971, DEB 1053573, and by the Office of Naval
Research under Grant No. N00014-08-1-1015.