A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs

Rahman, Md. Saidur and Nakano, Shin-Ichi and Nishizeki, Takao (1998) A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 99-110 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_54).

Full text not available from this repository.

Abstract

An orthogonal drawing of a plane graph G is a drawing of G in which each edge is drawn as a sequence of alternate horizontal and vertical line segments. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n^{7/4} \sqrt {log n}) for any plane graph of n vertices.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_54
Classifications:G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
G Algorithms and Complexity > G.560 Geometry
ID Code:172

Repository Staff Only: item control page

References

T.C. Biedl, Optimal orthogonal drawings of triconnected plane graphs, Proc. of SWAT '96, LNCS 1097 (1996), pp. 333-344.

A. Garg and R. Tamassia, On the computational complexity of upward and rectilinear planarity testing, Proc. of Graph Drawing '94, LNCS 894 (1995), pp. 286-297.

A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing, Proc. of Graph Drawing '96, LNCS 1190 (1997), pp. 201-226.

G. Kant, Drawing planar graphs using the canonical ordering, Algorithmica 16 (1996), pp. 4-32.

G. Kant and X. He, Two algorithms for finding rectangular duals of planar graphs, Proc. of WG'93, LNCS 790 (1994), pp. 396-410.

M.S. Rahman, S. Nakano and T. Nishizeki, Rectangular grid drawings of plane graphs, Proc. of COCOON'96, LNCS 1090 (1996), pp. 92-105. Also, Comp. Geom. Theo. Appl. (submitted).

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

C. Thomassen, Plane representations of graphs, (Eds.) J.A. Bondy and U.S.R. Murty, Progress in Graph Theory, Academic Press Canada, (1984), pp. 43-69.