Naslov
Drawing methods for 3-connected planar graphs

Autori
Orbanić, Alen ; Pisanski, Tomaž ; Boben, Mark ; Graovac, Ante

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
Book of Abstracts MATH/CHEM/COMP 2002 / Graovac, Ante; Pokrić, Biserka; Smrečki, Vilko - Zagreb : Institut Ruđer Bošković, 2002

Skup
MATH/CHEM/COMP 2002 - The 17th Dubrovnik International Course & Conference on the Interfaces among Mathematics, Chemistry and Computer Sciences

Mjesto i datum
Dubrovnik, Hrvatska, 24.06.2002. - 29.06.2002

Vrsta sudjelovanja
Poster

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
graph drawnings; planar 3-connected graphs; geometry of fullerenes and nanotubes; planarity of faces

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Kemija

POVEZANOST RADA