Rectangular Dualization of Biconnected Plane Graphs and Related Applications

Massimo Ancona, Sara Drago, Gianluca Quercini


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

Full Text:



Creative Commons License   Except where otherwise noted, content on this site is
  licensed under a Creative Commons 2.5 Italy License