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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/320

Actions (login required)

View Item View Item