Computing orthogonal drawings with the minimum number of bends

We describe a branch-and-bound algorithm for computing an orthogonal grid d rawing 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 sui te and compare the results with the state-of-the-art. The experiments show the feasibility of the approach and also its limitations. Further. the expe riments show how minimizing the number of bends has positive effects on oth er quality measures of the effectiveness of the drawing. We also present a new method for dealing with vertices of degree larger than four.