A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings of Biconnected Cubic Plane Graphs (Extended Abstract)

Nakano, Shin-Ichi and Yoshikawa, Makiko (2001) A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings of Biconnected Cubic Plane Graphs (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 296-307 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_28).

Full text not available from this repository.

Abstract

An orthogonal drawing of a plane graph G is a drawing of G with the given planar embedding in which each vertex is mapped to a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. Observe that only a planar graph with the maximum degree four or less has an orthogonal drawing. The best known algorithm to find an orthogonal drawing runs in time $O(n^{7/4}\sqrt {\log n})$ for any plane graph with n vertices. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given biconnected cubic plane graph with the minimum number of bends.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_28
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:408

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 Proc. of Workshop on Algorithms and Data structures, LNCS 709, Springer (1993) 151-162.

A. Garg and R. Tamassia, On the computational complexity of upward and rectilinear planarity testing, Proc. of Graph Drawing '94, LNCS 894, Springer (1995) 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, Springer (1997) 201-226.

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

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

M. S. Rahman, S. Nakano and T. Nishizeki, Rectangular grid drawings of plane graphs, Proc. of COCOON '96, LNCS 1090, Springer (1996) 92-105. Also, Computational Geometry: Theory and Applications, 10 (1998) 203-220.

M. S. Rahman, S. Nakano and T. Nishizeki, A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs, Journal of Graph Algorithms and Applications, 3 (1999) 31-62.

M. S. Rahman, S. Nakano and T. Nishizeki, Rectangular Drawings of Plane Graphs without Designated Corners, Proc. of COCOON '00, LNCS 1858, Springer (2000) 85-94.

R. Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM J. Comput., 16 (1987) 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) 43-69.