We describe a branch-and-bound algorithm for computing an orthogonal grid drawing with the minimum number of bends of a biconnected planar graph. Such an algorithm is based on an efficient enumeration schema of the embeddings of a planar graph and on several new methods for computing lower bounds of the number of bends. We experiment with such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show the feasibility of the approach and also its limitations. Further, the experiments show how minimizing the number of bends has positive effects on other quality measures of the effectiveness of the drawing. We also present a new method for dealing with vertices of degree larger than four.
Computing Orthogonal Drawings with the Minimum Number of Bends
DIDIMO, WALTER
2000
Abstract
We describe a branch-and-bound algorithm for computing an orthogonal grid drawing with the minimum number of bends of a biconnected planar graph. Such an algorithm is based on an efficient enumeration schema of the embeddings of a planar graph and on several new methods for computing lower bounds of the number of bends. We experiment with such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show the feasibility of the approach and also its limitations. Further, the experiments show how minimizing the number of bends has positive effects on other quality measures of the effectiveness of the drawing. We also present a new method for dealing with vertices of degree larger than four.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
