No-Bend Orthogonal Drawings of Series-Parallel Graphs

Rahman, Md. Saidur and Egi, Noritsugu and Nishizeki, Takao (2006) No-Bend Orthogonal Drawings of Series-Parallel Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 409-420 (Official URL: http://dx.doi.org/10.1007/11618058_37).

Full text not available from this repository.

Abstract

In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. Every series-parallel graph is planar. In this paper we give a linear-time algorithm to examine whether a series-parallel graph G of the maximum degree three has a no-bend orthogonal drawing and to find one if G has.

Item Type:Conference Paper
Additional Information:10.1007/11618058_37
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.720 Straight-line
ID Code:707

Repository Staff Only: item control page

References

F. Brandenburg, D. Eppstein, M. T. Goodrich, S. Kobourov, G. Liotta and P. Mutzel: Selected open problems in graph drawings, Proc. of GD '03, Lect, Notes in Computer Science, 1912, pp. 515-539, 2004.

G. Di Battista, G. Liotta and F. Vargiu: Spirality and optimal orthogonal drawings, SIAM J. Comput., 27(6), pp. 1764-1811, 1998.

G. Di Battista and R. Tamassia: On-line planarity testing, SIAM J. Comput., 25(5), pp. 956-997, 1996.

A. Garg and G. Liotta: Almost bend-optimal planar orthogonal drawings of biconnected degree-3 planar graphs in quadratic time, Proc. of GD '99, Lect. Notes in Computer Science, 1731, pp. 38-48, 1999.

A. Garg and R. Tamassia: On the computational comple

xity of upward and rectilinear planarity testing, SIAM J. Comput., 31(2), pp. 601-625, 2001.

T. Nishizeki and M. S. Rahman, Planar Graph Drawing, World Scientific, Singapore, 2004.

M. S. Rahman, N. Egi and T. Nishizeki: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs, IEICE Trans. Inf. & Syst., E88-D (1), pp.23-30, 2005.

M. S. Rahman and T. Nishizeki: Bend-minimum orthogonal drawings of plane 3-graphs, Proc. of WG '02, Lect. Notes in Computer Science, 2573, pp. 265-276, 2002.

M. S. Rahman, M. Naznin and T. Nishizeki: Orthogonal drawings of plane graphs without bends, Journal of Graph Alg. and Appl., 7(4), pp. 335-362, 2003.

M.S. Rahman, S. Nakano and T. Nishizeki: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs, Journal of Graph Alg. and Appl., 3(4), pp. 31-62, 1999. http://www.cs.brown.edu/publications/jgaa/

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