Abstract: MATH/CHEM/COMP 2002, Dubrovnik, June 24-29, 2002

 

 

Drawing Methods for 3-connected Planar Graphs

 

 

Alen Orbanic1, Tomaz Pisanski1, Marko Boben1, and Ante Graovac2

 

1IMFM, University of Ljubljana, Jadranska 19, SI-1000 Ljubljan, Slovenia

 

2Rudjer Boskovic Institute, POB 180, HR-10002 Zagreb, Croatia

 

 

 

According to Whitney, every 3-connected 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 3-connected planar graphs are exactly skeletons of convex 3D polyhedra. This means that the topological characterizations of Whitney extend to 3D geometrical representation. Tutte’s simple and efficient method can be lifted into 3D polyhedral drawing using methods involving Maxwell-Cremona 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.1-3 that the so-called Colin de Verdiere generalization of Laplace matrix could give very good polyhedral representations of 3-connected planar graphs.

Here algorithmic aspects of the problem are discussed. The algorithmic construction of convex polyhedron corresponding to planar 3-connected 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) 483-521.

2 L. Lovasz, A. Schrijver, Annales de lŽInstitut Fourier 49 (1999) 1017.

3 L. Lovasz, Journal of Combinatorial Theory B 82 (2001) 223-236.