Rectangular-radial drawings of cubic plane graphs

摘要

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.