Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract)

Bridgeman, Stina and Di Battista, Giuseppe and Didimo, Walter and Liotta, Giuseppe and Tamassia, Roberto and Vismara, Luca (1999) Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract). In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 8-26(Official URL: http://dx.doi.org/10.1007/3-540-46648-7_2).

Full text not available from this repository.


Given an orthogonal representation H with n vertices and bends, we study the problem of computing a planar orthogonal drawing of H with small area. This problem has direct applications to the development of practical graph drawing techniques for information visualization and VLSI layout. In this paper, we introduce the concept of turn-regularity of an orthogonal representation H, provide combinatorial characterizations of it, and show that if H is turn-regular (i.e., all its faces are turn-regular), then a planar orthogonal drawing of H with minimum area can be computed in O(n) time, and a planar orthogonal drawing of H minimum area and minimum total edge length within that area can be computed in O(n^{7/4} log n) time. We also apply our theoretical results to the design and implementation of new practical heuristic methods for constructing planar orthogonal drawings. An experimental study conducted on a test suite of orthogonal representations of randomly generated biconnected 4-planar graphs shows that the percentage of turn-regular faces is quite high and that our heuristic drawing methods perform better than previous ones.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_2
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/234

Actions (login required)

View Item View Item