Orthogonal Drawings of Plane Graphs without Bends

Rahman, Md. Saidur and Naznin, Mahmuda and Nishizeki, Takao (2002) Orthogonal Drawings of Plane Graphs without Bends. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 392-406 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_31).

Full text not available from this repository.

Abstract

In an orthogonal drawing of a plane graph G each vertex is drawn as a point and each edge is drawn as a sequence of vertical and horizontal line segments. A point at which the drawing of an edge changes its direction is called a bend. Every plane graph of the maximum degree at most four has an orthogonal drawing, but may need bends. A simple necessary and sufficient condition has not been known for a plane graph to have an orthogonal drawing without bends. In this paper we obtain a necessary and sufficient condition for a plane graph G of the maximum degree three to have an orthogonal drawing without bends. We also give a linear-time algorithm to find such a drawing of G if it exists.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_31
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:519

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

A. Garg and R. Tamassia. On the Computational Complexity of Upward and Rectilinear Planarity Testing. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 99-110.

A. Garg and R. Tamassia. A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In Proc. of the Symp. on Graph Drawing, GD'96,vol. 1190 of LNCS, pages 201-216. Springer Verlag, September 1996.

Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley and Sons, 1990.

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, S. Nakano, and T. Nishizeki. Rectangular drawings of plane graphs without designated corners. Proc. of COCOON '2000, LNCS 1858, pages 85-94, 2000. Also Comp. Geom. Theo. Appl., to appear.

M.S. Rahman, S. Nakano, and T. Nishizeki. Rectangular grid drawings of plane graphs. Comp. Geom. Theo. Appl., 10(3):203-220, 1998.

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

C. Thomassen. Planar representations of graphs. In: J.A. Bondy, U. S. R. Murty (eds.): Progress in Graph Theory. (1984) 43-69.

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