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

(a) (b)

Fig. 1. Two planar graphs with possible circle-contact representations: (a) a representation that is
not optimally balanced; (b) a perfectly-balanced representation

Gon¸alves et al. [14] prove that every 3-connected planar graph and its dual can be
simultaneously represented by touching triangles (and they point out that 4-connected
planar graphs also have contact representations with homothetic triangles). Also, Dun-
can et al. [9] show that every planar graph has a contact representation with convex
hexagons all of whose sides have one of three possible slopes, and that hexagons are
necessary for some graphs, if convexity is required. With respect to balanced circle-
contact representations, Breu and Kirkpatrick [4] show that it is NP-complete to test
whether a graph has a perfectly-balanced circle-contact representation, in which every
circle is the same size.

New Results. In this paper, we provide a number of positive and negative results re-
garding balanced circle-contact representations for planar graphs:

- Every planar graph with bounded maximumvertexdegree and logarithmic outer-
planarity admits a balanced circle-contact representation.
- There exist planar graphs with bounded maximumdegree and linear outerplanarity,
or with linear maximumdegree and bounded outerplanarity, that do not admit a
balanced circle-contact representation.
- Every tree admits a balanced circle-contact representation.
- Every outerpath admits a balanced circle-contact representation.
- Every cactus graph admits a balanced circle-contact representation.
- Every planar graph with bounded tree-depth admits a balanced circle-contact rep-
resentation.

2 Bounded Degree and Logarithmic Outerplanarity

Aplanegraph (that is, a combinatorially fixed planar embedding of a planar graph) is
outerplanar if all of its vertices are on the outer face. A k -outerplanar graph is defined
recursively. As a base case, if a plane graph is outerplanar, then it is a 1-outerplanar
graph. A plane graph is k -outerplanar, for k> 1, if the removal of all the outer vertices