Paper Info
Title
Rectangular drawings of plane graphs without designated corners
Abstract
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.
Year
DOI
Venue
2000
10.1016/S0925-7721(01)00061-X
Computational Geometry: Theory and Applications
Keywords
DocType
Volume
graph,algorithm,graph drawing
Conference
21
Issue
ISSN
ISBN
3
Computational Geometry: Theory and Applications
3-540-67787-9
Citations 
PageRank 
References 
10
0.80
7
Authors
3
Name
Order
Citations
PageRank
Md. Saidur Rahman134241.83
Shin-ichi Nakano224624.40
Takao Nishizeki31771267.08