Information Technology Reference
In-Depth Information
Balanced Circle Packings for Planar Graphs
Md. JawaherulAlam
1
, David Eppstein
2
, Michael T. Goodrich
2
,
Stephen G. Kobourov
1
,andSergey Pupyrev
1
,
3
1
Department of Computer Science, University of Arizona, Tucson, Arizona, USA
2
Department of Computer Science, University of California, Irvine, California, USA
3
Institute of Mathematics and Computer Science, Ural Federal University, Russia
Abstract.
We study
balanced
circle packings and circle-contact representations
for planar graphs, where the ratio of the largest circle's diameter to the smallest
circle's diameter is polynomial in the number of circles. We provide a number of
positive and negative results for the existence of such balanced configurations.
1
Introduction
Circle packings are a frequently used and important tool in graph drawing [3, 5, 10, 11,
18]. In this application, they can be formalized using the notion of a
circle-contact rep-
resentation
for a planar graph; this is a collection of interior-disjoint circles in
2
, corre-
sponding one-for-one with the vertices of the graph, such that two vertices are adjacent
if and only if their corresponding two circles are tangent to each other [15]. In a classic
paper, Koebe [16] proved that every triangulated planar graph has a circle-contact rep-
resentation, and this has been subsequently re-proved several times. Generalizing this,
every planar graph has a circle-contact representation: we can triangulate the graph by
adding “dummy” vertices connected to the existing vertices within each face, produce
a circle-contact representation for this augmented graph, and then remove the circles
corresponding to dummy vertices. It is not always possible to describe a circle-contact
representation for a given graph by a symbolic formula involving radicals [2, 5], but
they can nevertheless be constructed numerically and efficiently by polynomial-time
iterative schemes [7, 19].
One of the drawbacks of some of these constructions, however, is that the sizes of
the circles in some of these configurations may vary exponentially, leading to drawings
with very high area or with portions that are so small that they are below the resolu-
tion of the display. For this reason, we are interested in
balanced
circle packingsand
circle-contact representations for planar graphs, where the ratio of the maximumand
minimum diameters for the set of circles is polynomial in the number of vertices in the
graph; see Fig.1.
R
Related Work.
There is a large body of work about representing planar graphs as con-
tact graphs, where vertices are represented by geometrical objects and edges correspond
to two objects touching in some pre-specified fashion. For example, Hlinen ´y[15]stud-
ies contact representations using curves and line segments as objects. Several authors
have considered contact graphs of triangles of various types. For instance, de Frays-
seix
et al.
[12] show that every planar graph has a triangle-contact representation, and
