engleski

Drawing methods for 3-connected planar graphs

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 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. 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.

graph drawnings; planar 3-connected graphs; geometry of fullerenes and nanotubes; planarity of faces

nije evidentirano