Rectangular Dualization of Biconnected Plane Graphs and Related Applications

Autores/as

  • Massimo Ancona
  • Sara Drago
  • Gianluca Quercini

DOI:

https://doi.org/10.1685/

Resumen

Rectangular dualization is an effective visualization method for networks used in many optimization problems. However, only 4-connected triangulated planar graphs admit a rectangular dual. By adding special crossover vertices a plane graph G can be transformed in a new graph G' admitting a rectangular dual. In this paper we improve the result of a previous polynomial algorithm by presenting a linear method applicable to the class of plane bi-connected graphs. We also apply it to the hierarchical design and visualization of graphs and to the resolution of navigation issues in the design of 3D Virtual Worlds. [DOI: 10.1685 / CSC06009] About DOI

Descargas

Publicado

2007-10-01

Número

Vol. 1 (2006)

Sección

Articles

Licencia

Authors who submit to this journal agree to the following terms: a) Authors retain copyright over their work, while allowing the SIMAI to place this accepted work under a Creative Commons Attribution License (CC license), which allows others to freely access, use, and share the work, with an acknowledgement of the work's authorship. b) Authors are able to waive the terms of the CC license and enter into separate, additional contractual arrangements for the non-exclusive distribution and subsequent publication of this work (e.g., publish a revised version in a journal, post it to an institutional repository or publish it in a book). with an acknowledgement of its initial publication on “Communications to SIMAI Congress”. c) In addition, authors are encouraged to post and share their work online (e.g., in institutional repositories or on their website).