No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs (Extended Abstract)

Rahman, Md. Saidur and Egi, Noritsugu and Nishizeki, Takao (2004) No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs (Extended Abstract). In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 387-392 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_36).

Full text not available from this repository.

Abstract

A plane graph is a planar graph with a fixed embedding. 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. In this paper we consider a class of planar graphs, called subdividions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_36
Classifications:M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:468

Repository Staff Only: item control page

References

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

A. Garg and R. Tamassia, On the computational complexity of upward and rectilinear planarity testing, SIAM J. Comput., 31(2), pp. 601-625, 2001.

T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, North-Holland, Amsterdam, 1988.

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, T. Nishizeki, and S. Ghosh, Rectangualr drawings of planar graphs, Proc. of GD '02, Lecture Notes in Copmputer Science, 2528, pp.244-255, 2002, also Journal of Algorithms, to appear.

M. S. Rahman, S. Nakano and T. Nishizeki, Box-rectangular drawings of plane graphs, Journal of Algorithms, 37, pp. 363-398, 2000.

M. S. Rahman, M. Naznin and T. Nishizeki, Orthogonal drawings of plane graphs without bends, Proc. of Graph Drawing '01, Lecture Notes in Computer Science, Springer-Verlag, 2265, pp. 392-406, 2002, also Journal of Graph Alg. and Appl., to appear.

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., http://www.cs.brown.edu/publications/jgaa/,3(4) pp. 31-62, 1999.

J. Storer, On minimum node-cost planar embeddings, Networks, 14, pp. 181-212, 1984.

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