An Experimental Comparison of Orthogonal Compaction Algorithms (Extended Abstract)

Klau, Gunnar W. and Klein, Karsten and Mutzel, Petra (2001) An Experimental Comparison of Orthogonal Compaction Algorithms (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 37-51(Official URL:

Full text not available from this repository.


We present an experimental study in which we compare the state-of-the-art methods for compacting orthogonal graph layouts. Given the shape of a planar orthogonal drawing, the task is to place the vertices and the bends on grid points so that the total area or the total edge length is minimised. We compare four constructive heuristics based on rectangular dissection and on turn-regularity, also in combination with two improvement heuristics based on longest paths and network flows, and an exact method which is able to compute provable optimal drawings of minimum total edge length. We provide a performance evaluation in terms of quality and running time. The test data consists of two test-suites already used in previous experimental research. In order to get hard instances, we randomly generated an additional set of planar graphs.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-44541-2_5
Classifications: G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar

Actions (login required)

View Item View Item