Computing orthogonal drawings with the minimum number of bends
Paola Bertolazzi, Giuseppe Di Battista, Walter Didimo · Lecture notes in computer science · 1997
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 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 such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show how minimizing the number of bends strongly improves several quality measures of the effectiveness of the drawing. We also present a graphic tool with animation that embodies the algorithm and allows interacting with all the phases of the computation.