Rectangular Drawings of Planar Graphs (Extended Abstract)

Rahman, Md. Saidur and Nishizeki, Takao and Ghosh, Shubhashis (2002) Rectangular Drawings of Planar Graphs (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 244-255 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_23).

Full text not available from this repository.

Abstract

A plane graph is a planar graph with a fixed embedding. In a rectangular drawing of a plane graph, each vertex is drawn as a point, each edge is drawn as a horizontal or vertical line segment, and each face is drawn as a rectangle. A planar graph is said to have a rectangular drawing if at least one of its plane embeddings has a rectangular drawing. In this paper we give a linear-time algorithm to examine whether a planar graph G of the maximum degree three has a rectangular drawing or not, and to find a rectangular drawing of G if it exists.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_23
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.999 Others
P Styles > P.540 Planar
ID Code:320

Repository Staff Only: item control page

References

J. Bhasker and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Algorithmica, 3, pp. 247-278, 1988.

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

X. He, On finding the rectangular duals of planar triangulated graphs, SIAM J. Comput, 22(6), pp. 1218-1226, 1993.

X. He, A simple linear time algorithm for proper box rectangular drawings of plane graphs, Journal of Algorithms, 40(1), pp. 82-101, 2001.

J.E. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput., 2(3), pp. 135-158, 1973.

G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoretical Computer Science, 172, pp. 175-193, 1997.

K. Kozminski and E. Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for VLSI integrated circuits, Proc. 21st DAC, Albuquerque, pp. 655-656, 1984.

T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, John Wiley & Sons, Chichester, 1990.

S. Munemoto, N. Katoh and G. Imamura, Finding an optimal floor layout based on an orthogonal graph drawing algorithm, J. Archit. Plann. Enviroment Eng. AIJ, No. 524, pp. 279-286, 2000.

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

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

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. Appl., 3, No. 4, pp. 31-62, 1999.

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

M.S. Rahman, S. Nakano and T. Nishizeki, Rectangular drawings of plane graphs without designated corners, Comp. Geom. Theo. Appl., 21(3), pp. 121-138, 2002.

K. Tani, S. Tsukiyama, S. Shinoda and I. Shirakawa, On area-efficient drawings of rectangular duals for VLSI floor-plan, Mathematical Programming, 52, pp. 29-43, 1991.

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

C. Thomassen, Plane cubic graphs with prescribed face areas, Combinatorics, Probability and Computing, 1, pp. 371-381, 1992.

P. Ungar, On diagrams representing maps, J. London Math. Soc., 28, pp. 336-342, 1953.