Abstract: MATH/CHEM/COMP 2002, Dubrovnik,
June 2429, 2002

Drawing Methods
for 3connected Planar Graphs Alen Orbanic^{1}, Tomaz Pisanski^{1}, Marko Boben^{1},
and Ante Graovac^{2} ^{1}IMFM,
University of Ljubljana, Jadranska 19, SI1000 Ljubljan, Slovenia ^{2}Rudjer Boskovic Institute, POB 180, HR10002 Zagreb, Croatia According to Whitney, every
3connected planar graph admits a unique embedding in the sphere or,
equivalently, in the plane. Tutte showed that the combinatorial information
is sufficient for providing a straight line planar embedding. In 1922
Steinitz proved that 3connected planar graphs are exactly skeletons of
convex 3D polyhedra. This means that the topological characterizations of
Whitney extend to 3D geometrical representation. Tuttes simple and efficient
method can be lifted into 3D polyhedral drawing using methods involving
MaxwellCremona stress theorem. The Laplace method for graph
drawing proved to be suitable for 3D representations of some classes of
graphs. However, there are no guaranties that the faces in such
representations are planar. Recently it was proved by Lovasz et al.^{13 }that
the socalled Colin de Verdiere generalization of Laplace matrix could give
very good polyhedral representations of 3connected planar graphs. Here algorithmic aspects of the
problem are discussed. The algorithmic construction of convex polyhedron
corresponding to planar 3connected graph has numerous applications in
crystallography and chemistry. Especially interesting should be applications
to plausible geometry determination in fullerenes and carbon nanotubes. ^{1} A. Kotlov, L. Lovasz, S. Vempala, Combinatorica 17
(1997) 483521. ^{2} L. Lovasz, A. Schrijver, Annales de lŽInstitut Fourier 49
(1999) 1017. ^{3} L. Lovasz, Journal of Combinatorial Theory B 82 (2001)
223236. 