History


Please fill in your query. A complete syntax description you will find on the General Help page.
Rectangular drawings of plane graphs without designated corners. (English)
Comput. Geom. 21, No.3, 121-138 (2002).
Summary: This paper addresses the problem of finding rectangular drawings of plane graphs, in which each vertex is drawn as a point, each edge is drawn as a horizontal or a vertical line segment, and the contour of each face is drawn as a rectangle. A graph is a 2-3 plane graph if it is a plane graph and each vertex has degree 3 except the vertices on the outer face which have degree 2 or 3. A necessary and sufficient condition for the existence of a rectangular drawing has been known only for the case where exactly four vertices of degree 2 on the outer face are designated as corners in a 2-3 plane graph $G$. In this paper we establish a necessary and sufficient condition for the existence of a rectangular drawing of $G$ for the general case in which no vertices are designated as corners. We also give a linear-time algorithm to find a rectangular drawing of $G$ if it exists.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!