Rectangular-radial drawings of cubic plane graphs
Date
2010
Authors
Hasheminezhad, Mahdieh
Hashemi, S Mehdi
McKay, Brendan
Tahmasbi, Maryam
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
Rectangular drawings and rectangular duals can be naturally extended to other surfaces. In this paper, we extend rectangular drawings and rectangular duals to drawings on a cylinder. The extended drawings are called rectangular-radial drawings and rectangular-radial duals. Rectangular-radial drawings correspond to periodic rectangular tilings of a 1-dimensional strip. We establish a necessary and sufficient condition for plane graphs with maximum degree 3 to have rectangular-radial drawings and a necessary and sufficient condition for triangulated plane graphs to have rectangular-radial duals. Furthermore, we present three linear time algorithms under three different conditions for finding a rectangular-radial drawing for a given cubic plane graph, if one exists.
Description
Keywords
Keywords: Cubic graph; Linear-time algorithms; Maximum degree 3; Plane graphs; Radial drawings; Sufficient conditions; Mathematical techniques Cubic graph; Ortho-radial grid; Rectangular drawing; Rectangular dual; Rectangular-radial drawing
Citation
Collections
Source
Computational Geometry: Theory and Applications
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31