Loading…

Bend Minimization in Planar Orthogonal Drawings Using Integer Programming

We consider the problem of minimizing the number of bends in a planar orthogonal graph drawing. While the problem can be solved via network flow for a given planar embedding of a graph, it is NP-hard if we consider all planar embeddings. Our approach for biconnected graphs combines a new integer lin...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2006-01, Vol.17 (3), p.665-687
Main Authors: Mutzel, Petra, Weiskircher, René
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of minimizing the number of bends in a planar orthogonal graph drawing. While the problem can be solved via network flow for a given planar embedding of a graph, it is NP-hard if we consider all planar embeddings. Our approach for biconnected graphs combines a new integer linear programming (ILP) formulation for the set of all embeddings of a planar graph with the network flow formulation of the bend minimization problem for fixed embeddings. We report on extensive computational experiments with two benchmark sets containing a total of more than 12,000 graphs where we compared the performance of our ILP-based algorithm with a heuristic and a previously published branch & bound algorithm for solving the same problem. Our new algorithm is significantly faster than the previously published approach for the larger graphs of the benchmark graphs derived from industrial applications and almost twice as fast for the benchmark graphs from the artificially generated set of hard instances.
ISSN:1052-6234
1095-7189
DOI:10.1137/040614086