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, Štirín Castle, Czech Republic , 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
ID Code:236

Repository Staff Only: item control page

References

G. Di Battista, G. Liotta, and F. Vargiu. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs. In Proc. Workshop Algorithms Data Struct., volume 709 of Lecture Notes Comput. Sci., pages 151-162. Springer-Verlag, 1993.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD '94), volume 894 of Lecture Notes Comput. Sci., pages 286-297. Springer-Verlag, 1995.

A. Garg and R. Tamassia. A new minimum cost flow algorithm with applications to graph drawing. In S. C. North, editor, Graph Drawing (Proc. GD '96), Lecture Notes Comput. Sci. Springer-Verlag, 1997.

A. Papakostas and I. G. Tollis. Improved algorithms and bounds for orthogonal drawings. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD '94), volume 894 of Lecture Notes Comput. Sci., pages 40-51. Springer-Verlag, 1995.

M. S. Rahman, S. Nakano, and T. Nishizeki. A linear algorithm for optimal orthogonal drawings of triconnected cubic planar graphs. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Computer Science, pages 99-110. Springer-Verlag, 1998.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.