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...
Saved in:
Published in: | SIAM journal on optimization 2006-01, Vol.17 (3), p.665-687 |
---|---|
Main Authors: | , |
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!
|
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 |