Almost Bend-Optimal Planar Orthogonal Drawings of Biconnected Degree-3 Planar Graphs in Quadratic Time

Garg, Ashim and Liotta, Giuseppe (1999) Almost Bend-Optimal Planar Orthogonal Drawings of Biconnected Degree-3 Planar Graphs in Quadratic Time. In: September 15-19, 1999, September 15-19, 1999 , pp. 38-48(Official URL: http://dx.doi.org/10.1007/3-540-46648-7_4).

Full text not available from this repository.

Abstract

Let G be a degree-3 planar biconnected graph with n vertices. Let Opt(G) be the minimum number of bends in any orthogonal planar drawing of G. We show that G admits a planar orthogonal drawing D with at most Opt(G)+3 bends that can constructed in O(n^{2}) time. The fastest known algorithm for constructing a bend-minimum drawing of G has time-complexity O(n^{5} log n) and therefore, we present a significantly faster algorithm that constructs almost bend-optimal drawings.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_4
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/236

Actions (login required)

View Item View Item