Extended Rectangular Drawings of Plane Graphs with Designated Corners (Extended Abstract)

Miura, Kazuyuki and Miyazawa, Ayako and Nishizeki, Takao (2002) Extended Rectangular Drawings of Plane Graphs with Designated Corners (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 256-267 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_24).

Full text not available from this repository.

Abstract

In a rectangular drawing of a plane graph, each edge is drawn as a horizontal or vertical line segment, and all faces including the outer face are drawn as rectangles. In this paper, we introduce an $\lq\lq$extended rectangular drawing" in which all inner faces are drawn as rectangles but the outer face is drawn as a rectilinear polygon with designated corners, and give a necessary and sufficient condition for a plane graph to have an extended rectangular drawing.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_24
Classifications:Z Theory > Z.750 Topology
Z Theory > Z.250 Geometry
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:251

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis, Graph Drawing, Prentice Hall, NJ (1999).

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

A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing, Proc. of Graph Drawing'96, Lect. Notes in Computer Science, 1190, pp. 201-206, 1997.

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

X. He, On floor-plan of plane graphs, SIAM J. Comput., 28, 6, pp. 2150-2167, 1999.

G. Kant and X. He, Regular edge-labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoret. Comput. Sci., 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. of 21st DAC, Albuquerque, pp. 655-656, 1984.

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

M.S. Rahman, S. Nakano and T. Nishizeki, Rectangular drawings of plane graphs without designated corners, Computational Geometry, 21, pp. 121-138, 2002.

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

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