Rectangular Dualization of Biconnected Plane Graphs and Related Applications
Abstract
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
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:
PDFDOI: https://doi.org/10.1685/
Except where otherwise noted, content on this site is licensed under a Creative Commons 2.5 Italy License