Informatica 28 (2004) 239-243 239
Algorithms for Drawing Polyhedra from 3-Connected Planar Graphs
Alen Orbanic, Marko Boben, Gašper Jaklic and Tomaž Pisanski IMFM, OTR, Jadranska 19, Ljubljana, Slovenia
Emails: Alen.Orbanic@fmf.uni-lj.si, Marko.Boben@fmf.uni-lj.si, Gasper.Jaklic@fmf.uni-lj.si, Tomaz.Pisanski@fmf.uni-lj.si
Keywords: graph drawing, Tutte's drawing method, representation of a graph, polyhedral representations Received: September 15, 2003
Two algorithms for producing polyhedral representations for 3-connected planar graphs are discussed in the paper. One of them uses Tutte's drawing algorithm [11] to produce a 2D drawing. Then the drawing is lifted into 3D space obtaining a polyhedral embedding. The other is a simple algorithm by G. Hart [4] for drawing canonical polyhedral representations. Some alternative aspects (physical model, Markov chain model) in algorithms for obtaining Tutte's drawings are presented and proved.
Povzetek: članek opisuje dva pristopa za grafičen prikaz planarnih grafov.
1 Introduction
A convex polyhedron can be viewed as a convex hull of its vertices and referred as P = (pi,..., p„), e R3, or as an intersection of the half-spaces defined by the supporting planes of the faces using the side of R3 that contains the polyhedron. These are two dual definitions. For more detailed and generalized definitions of polyhedra see [12].
Any graph mentioned in the article is 3-connected planar. Vertices and edges of a polyhedron P define a skeleton graph G(P) in an obvious way. The skeleton graph is obviously planar. By Balinski's theorem [12] this graph is 3-connected. In 1922 Steinitz proved that 3-connected planar graphs are exactly the skeletons of the convex 3D polyhedra. According to Whitney [2], every 3-connected planar graph has a unique embedding in the plane and the faces of the embedding are exactly the non-separating induced cycles. These faces are exactly the faces of any polyhedron with the same skeleton graph.
Given a 3-connected graph G one would like to have an algorithm to obtain a polyhedron with its skeleton G. We will call such a representation a polyhedral representation. A graph is given as a combinatorial structure and our algorithms return 3D coordinates of the vertices of the polyhedron. There are infinitely many polyhedral representations for a given graph. According to Koebe [5], for each polyhedron there is the canonical form, which is determined up to a rotation in 3D space. The canonical representation is especially "nice" because it possesses maximal possible geometric symmetry. Each edge of such a polyhedron touches the unit sphere in exactly one point and the center of the gravity of these touching points is the origin. If a polyhedron P is in canonical form, then the polar polyhedron is also in canonical form and the dual edges have the same touching points with the unit sphere. For a given polyhe-
dron P containing the origin of R3 a polar polyhedron P * is well defined and unique:
P * = {y G R3 | {x, y) < 1 for all x G P}.
A skeleton graph of P *, G* := G (P *) is exactly the dual graph of the skeleton graph G := G (P).
We will present some methods together with references for more detailed information. 1
2 Tutte's algorithm
The proofs and detailed descriptions can be found in [10] and [11].
In 1963 Tutte [11] invented an interesting rubber-band method for embedding a 3-connected planar graph G into the plane. By this method one face C (on vertices k + 1,... ,n, referred as the outer cycle) of a graph is embedded into the plane as a fixed strictly convex polygon, while the other adjacent vertices are connected with rubber-bands. On the edge ij, where i,j not both in C, there is a strictly positive stretching coefficient uij. Later we will also assign the weights uij to edges ij G C, but we will not use them in the Tutte's method. Let pi represent a position of the vertex i in the plane. The positions pi := p0, i = k+1,... ,n are fixed. The other positions are to be calculated and lie somewhere inside the polygon. The system consisting of a rigid polygon as a frame and rubber-bands is in equilibrium if the following system of equations holds:
]T Uij (Pj - Pi) = o, i G v (G) - v (C), (1)
ijeE(G)
Pi = P0, i g V (C).
1 Supported in part by Ministrstvo za šolstvo, znanost in šport Republike Slovenije, grant J1-6161, J2-6193.
240 Informática 28 (2004) 239-243
A. OrbaniC et al.
Tutte proved that this system has a unique solution which gives a set of positions that induces a straight line embedding of G into the plane with convex faces. Instead of solving the system of the linear equations directly, two alternative approaches can be used.
In [8] the following algorithm called Schlegel diagram was introduced:
Algorithm 1 Fix the positions of the vertices of the outer cycle C on a convex polygon in R2. Assign to the other vertices random positions inside the polygon. For those vertices repeat the following steps:
-	for each vertex i calculate the resulting force Fi of all adjacent rubber-bands;
-	move each vertex i for vector aFi, where a > 0 is a fixed real number;
until the displacements of all vertices are sufficently small (depends on the prescribed precision of the drawing).
We will determine the values of a which guarantee the convergence of Algorithm 1.
A weighted Laplacian matrix Qu for a graph G on n vertices and weights w = (wij )ijeE(G) is a n x n matrix with Q )i,j = (Qu )j,i = -wjj when ij e E(G), (Qu )i,j = 0, when i = j, and ij £ E(G) and (Qu )M =
-E
n
j=1,j=i
(Qu)i,j. Let K = {!,..., k} and Qu,k be a
matrix that consists of the first k rows of Qu. Let
A
-Qu,
u,K
k,n-k
-I
n-k
(2)
Ax = b,
Ay
(3)
The iteration procedure in the Algorithm 1 can be rewritten as:
xn+i = xn + a(Axn - b),
yn+1 = yn + a(Ayn - c).
(4)
Let us determine the bounds for a that ensure that the algorithm converges. It is sufficient to do this for the iteration for x. Let us rewrite the iteration (4):
cn+1 = (aA + I)xn - ab.
Let p(M ) denote a spectral radius of a matrix M : It is well known that an iteration of this type converges iff p(aA + I) < 1, see [1]. We will show that for a sufficiently small a > 0 it follows p(aA + I) < 1.
If a(A) is the spectrum of the matrix A, then (with slight abuse of notation) a(aA +1) = 1+ a(aA) = 1 + a ■ a(A). Proving that a(A) is strictly negative would yield the existence of the appropriate a, such that p(aA + I) < 1. The matrix A is block diagonal and upper triangular with two diagonal blocks -Qu,{k,k) and -Ik, where Qu,(k,k) is a matrix obtained from Qu taking the rows and the columns in the set K in induced order. It follows that ff(A) = v(-Qu,(k,k)) u a(-Ik). It suffices to show that Qu,(k,k) is positive definite.
The matrix QU,(K,K) is a principal sub-matrix of Qu. We will prove that a(Qu) > 0 and that QU,(K,K) is nonsingular. Cauchy's interlacing theorem [1] implies that Qu,(k,k) is also positive definite.
Using the Gershgorin's theorem (see [1]) it is easy to see that the eigenvalues of Laplacian matrix Qu are contained in [0, 2 ■ m.sxi=i..,n{(Qu)¿,¿}i, hence a(Qu) > 0. By Whitney's theorem H = G - C is connected. Let Q' := Qu (H) be a weighted Laplacian matrix of H and Q := Qu,(k,k). Then: Q = Q' + A, where A is a nonnegative diagonal matrix. Since G is connected, A = 0. For an arbitrary vector w e Rk:
wT Qw
nQ'w + wT Aw.
where 0knn-k represents a k x (n — k) zero matrix and Ii a i x i identity matrix. Let x = (x\,..xn) and y = (y!,...,yn), where pi = (xj,yj). Let pi := p0 be fixed values for i = k + 1,... ,n and pi be the pairs of variables for i = 1,...,k. Let also b = (&i,..., bn), c = (c1,..., cn) and (bi, ci) = (0,0) for i = 1,...,k and (bi, ci) = — p0 for i = k + 1,..., n. The system of equations (1) can be written as:
Since eigenvalues of Q' are by Gershgorin's theorem contained in the interval [0, 2 ■ maxi=1.,.,k {Qi^j], it follows that wTQ'w > 0. Since H is connected, the multiplicity of the smallest eigenvalue is 1. But the smallest eigenvalue is 0 and its eigenvector is the all ones vector 1. Therefore wTQ'w = 0 iff w = c 1 for some c e R. Since A is a nonnegative diagonal matrix, it follows that wT Aw > 0. But for w = 1, wTAw = c21TA1 > 0, if c = 0. So wTQw > 0 for each w = 0 and Q is positive definite. The following theorem holds:
THEOREM 1 Let G be a 3-connected planar graph. If:
2
0 < a <-7-7-YT'
max j1, 2 ■ maxi=i,...k\T.ijeE{G) j)
then Algorithm 1 converges to the solution of (1).
The other alternative approach comes from probability. Let us define a Markov chain X0,X1,... with transition matrix P using the graph G and the weights w:
0
Pi

E,
keE(G) '
ij £ E(G),
ij £ e(G) - E(C), (6) ij £ E(C).
(5) After rewriting the system (1) we get:
pi =^^0) ^^ • , i £ y (G) - y (c (7)
E
ijeE(G) Uij
Pi = Pi,
i £ V(C).
w
c.
Ui

ALGORITHMS FOR DRAWING POLYHEDRA
Informatica 28 (2004) 239-243 241
or
Px = x,
p y = y,
Pi = p0 = (X0,y0),
(8)
i e V(C).
The vertices of the graph G are the states of the Markov chain. Let A c V(G). The values:
hA = Pr(Xr e A for some r > 0 | X0 = i), (9)
are hitting probabilities for the set A when starting in the state i. We will write hj for h{j}. The following theorem holds (see [7]):
Theorem 2 A vector hA = (hA,... ,h£) is a solution of a system:
1.	hA = l,for i e A,
2.	E;=i Pij hA = hA, for i /A,
3.	0 < hA < 1 for all i.
If hA is any other solution then hA < hA (inequality on components). Therefore hA is a minimal solution.
Let hj = (hj )n=1 be the vector of hitting probabilities. By Theorem 2, Phj = hj. Let J = [hk+1, ..., hn] be a matrix with vectors hj as columns. Hence PJ = J.
Let x0 = (xl+i,...,x°n) and y0 = (y0+i,..., y00) be the coordinates of vertices on the outer polygon. Then:
PJ x0 = Jx0,
PJ y0 = Jy0,
(10)
and
(Jx )j = x0,
(Jy0)j = yj, j = k + !,.....
(11)
Thus pi = (( Jx0)i, (Jy0)i) is a solution of the system (7) and it is unique by Tutte.
The following theorem holds:
Theorem 3 Let G = ({1, ...,n}, E (G)) be a 3-connec-ted planar graph, C = (k + 1,... ,n) be one of its faces, and p0, i = k + 1,... ,n, be the fixed coordinates of the vertices of C forming a convex polygon in the cyclical order of C. Let P be a transition matrix for the Markov chain (Xr) and let hj be the hitting probabilities for entering into vertices j = k + 1,... ,n, starting from the vertex i e V(G). Then the Tutte's drawing can be obtained in the following way:
Pi = £ hjp°, j=k+i
pi = pi0,
i e V(G) - V(C), i e V(C).
The theorem was originally conjectured by T. W. Tucker. To obtain the hitting probabilities hj one can make suffi-cently large number of the following experiments: start in i and make a series of steps until a state in C is reached. The frequency of the walks ending in j is an approximation for hj.
It can be easily verified that
\im(Pn)ij = hj, i /C,j e C.
n—
Hence the hitting probabilities can be obtained by calculating Pr, r large.
3 Lifting of a Tutte's Drawing
A detailed procedure with proofs can be found in [10].
A weighted embedded 3-connected planar graph G with weights w and positions p1;..., pn of the vertices is in equilibrium if:
wij(pj - pi) = 0, for all i e V(G). (12)
ijeE(G)
The corresponding weight w is called an equilibrium weight. Maxwell-Cremona's theorem states that if for an embedded 3-connected graph with convex faces there exists an equilibrium weight with strictly negative weights on the edges of the outer face and strictly positive weights on the inner edges, then the drawing can be lifted to a polyhedron. A Tutte's drawing with the corresponding weights on the edges that are not in the outer face has all the vertices not on the outer face in an equilibrium. To use a Maxwell-Cremona's theorem there should be negative equilibrium weights on the edges of the outer face. A simplified version of the theorem will be used to solve that problem.
Proposition 4 Let G be a 3-connected planar graph embedded with one outer face f1 on a convex polygon with all other faces (f2,..., fm) as convex polygons inside the outer polygon. Let G* be the geometric dual of G. Let e = ij e E(G) and let e* = fg be the corresponding dual edge, such that if one traverses from i to j in the embedding of G, the face f is on the left side. Let (i, j, f, g) denote an oriented patch and let q^ = (0,0,0). Then for 2 < k < m the unique assignments q/fc exist, such that:
qf - qs = wij (pi x pj),
where w is an equilibrium weight and x denotes a cross product.
For the proof see [10].
Using vectors q one can define a function on the interior of the outer polygon:
z(x) = (x, qf,), for x e fi C R2.
(13)
It can be proved that the function z(x) is linear, continuous, convex, and the image of each face lies on some plane. It
242 Informatica 28 (2004) 239-243
A. OrbaniC et al.
can be seen that if we have a Tutte's drawing with a triangle as the outer face, then using (12) on the Tutte's drawing, one can calculate the remaining negative weights on the edges of the triangle. The surface defined by the graph of the function z(x) together with a patch in the place of the triangle determines a hull of the polyhedral representation of G. Using the fact that if G is 3-connected planar then either G or G* has a triangle as a face (see [6]). This implies the following algorithm:
Algorithm 2 1. Determine the faces of G (some pla-narity algorithm).
2.	If one of the faces is a triangle, use G otherwise use
G*.
3.	Draw a Tutte's drawing.
4.	From the Tutte's drawing and using Proposition 4 determine vectors q.
5.	Determine the vertices of the polyhedron using the function z(x).
6.	If G was used, we have a polyhedral embedding. Otherwise move the polyhedron so that the center of the gravity of the vertices lies in the origin. Calculate the polar polyhedron.
Figure 1: Dodecahedron and Fullerene C60 drawn by Tutte's method.
4 Canonical polyhedra
To produce the canonical polyhedral representation one can use methods for determining primal-dual circle packing (PDCP) of 3-connected planar graph. Having PDCP one can easily obtain the canonical polyhedral representation using the inverse of the stereographic projection on the unit sphere. One of the algorithms is due to Mohar [6] (circle packing in the plane or on the sphere). The other, which works in 3D and on more or less small graphs, is due to G. Hart [4]. We present some slight improvements for the latter algorithm. The Hart's algorithm reads:
Algorithm 3 1. Start with a "good approximation" of a polyhedron that has edges as near as possible to the unit sphere. For instance, get the representation
from the Algorithm 2, move the center of gravity into the origin, and project vertices from the origin to the unit sphere.
2. Repeat the following procedure until the positions of the vertices are precise enough:
(a)	for each edge e calculate the point pe, which is the closest to the origin. If the edge is not at the distance 1 to the origin, move the endpoints of e foravector a(l — ||pe||)pe, where 0 < a < 1.
(b)	for each face calculate the approximate plane of the vertices on the face. If some vertex v is at the distance d(v) from the plane, move v towards the plane in the direction of the normal for a magnitude (3d(v), 0 < ¡3 < 1.
Algorithm 3 works well on small graphs. It seems to work well on cubic graphs and perhaps on graphs with lower degrees of the vertices, but the convergence might be poor, especially on the larger graphs. It behaves very poorly (does not even converge) if degrees are rather high (> 4). More or less we tested the performance on cubic graphs. If the cubic graph is large the convergence is very poor. To improve the convergence on cubic graphs we first use Algorithm 3 for a few iterations. Then at each iteration we calculate the vertices of the approximate polar (from approximate faces) and the dual edges. Then we check if the current dual edges are perpendicular to the original edges. If not, the vertices are moved in a manner of rotation for some small magnitude that depends on the difference between the current angle and n/2. This brings a small improvement to the convergence of the algorithm.
Both methods significantly depend on a, 3 and similar parameters in the improved algorithm. Unfortunately we were not able to prove the convergence for any set of the parameters.
Figure 2: A dodecahedron obtained by lifting Tutte's drawing of its dual graph (left) and a dodecahedron in the canonical form (right).
ALGORITHMS FOR DRAWING POLYHEDRA
Informatica 28 (2004) 239-243 241
References
[1]	J. W. Demmel, Applied numerical linear algebra, SIAM Society for Industrial and Applied Mathematics, 1997.
[2]	R. Diestel, Graph Theory, Springer, 1997.
[3]	C. D. Godsil, G. F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, 207, SpringerVerlag, 2001.
[4]	G. W. Hart, Calculating Canonical Polyhedra, Math-ematica in Education and Research, Vol 6 No. 3, Summer 1997, pp. 5-10.
[5]	P. Koebe, Kontaktprobleme der Konformen Abbildung, Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88 (1936), 141-164.
[6]	B. Mohar, A polynomial time circle packing algorithm, Discrete Math. 117 (1993), 257-263.
[7]	J. Norris, Markov Chains, Cambridge University Press, 1999.
[8]	T. Pisanski, B. Plestenjak, A. Graovac: NiceGraph Program and its Applications In Chemistry, Croat. Chem. Acta 68 (1995), 283-292.
[9]	T. Pisanski et al., VEGA program, http://vega.ijp.si/Htmldoc/Vega03.html
[10]	J. Richter-Gebert, Realization Spaces of Polytopes, Lecture Notes in Mathematics, Vol. 1643, SpringerVerlag, Berlin, 1996.
[11]	W.T. Tutte, How to draw a graph, Proc. London Math. Soc. 13 (1963), 743-767.
[12]	G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York 1995, Revised edition 1998.