Information Technology Reference
In-Depth Information
Fig. 6. The graph Bipyramid(7) and its associated concentric circle packing
5
Impossibility Results for Circle Packings
Root Computation Trees. A given graph may be represented by infinitely many circle
packings, related to each other by M obius transformations. But as we now show, if one
particular packing cannot be constructed in our model, then there is no other packing
for the same graph that the model can construct.
Lemma 11. Suppose that a circle packing P containstwoconcentric circles. Suppose
also that atleast oneradiusofa circle or distance between twocirclecenters, atleast
onecenter of a circle, andthe slope of atleast onelineconnecting twocenters of
circles in P can all be constructed by oneofourcomputationmodels, butthat P itself
cannot be constructed. Then thesame model cannot construct any circle packing that
represents thesame underlying graphas P .
Proof. Suppose for a contradiction that the model could construct a circle packing Q
representing the same graph as P .ByLemma3itcould transform Q to make the two
circles concentric, giving a packing that is similar either to P or to the inversion of P
through the center of the concentric circles. By one more transformation it can be made
similar to P . The model could then rotate the packing so the slope of the line connecting
two centers matches the corresponding slope in P , scale it so the radius of one of its
circles matches the corresponding radiusin P , and translate the center of one of its
circles to the corresponding center in P ,resulting in P itself. This gives a construction
of P , contradicting the assumption.
We d e fi n e Bipyramid( k ) to be the graph formed by the vertices and edges of a
( k +2)-vertex bipyramid (a polyhedron formed from two pyramids over a k -gon by
gluing them together on their bases). In graph-theoretic terms, it consists of a k -cycle
and two additional vertices, with both of these vertices connected by edges to every
vertex of the k -cycle. The example of Bipyramid(7) can be seen in Figure 6, left.
Theorem 7. There exists agraphwhose circle packingscannot be constructed bya
quadratic computation tree.
Proof. Consider the circle packing of Bipyramid(7) in which the two hubs are repre-
sented by concentric circles, centered at the origin, with the other circle centers all on
the unit circle and with one of them on the x axis. One of the centers of this packing
is at the root of unity ʶ 7 . By Lemma 6, [ Q ( ʶ 7 ): Q ]= ˆ (7) = 6. 6 is not a power
of two, so by Lemma 5 ʶ 7 cannot be constructed by a quadratic computation tree. By
Lemma 11, neither can any other packing for the same graph.
Search WWH ::




Custom Search