Rectangular-radial drawings of cubic plane graphs
详细信息 查看全文
- 作者：Mahdieh Hasheminezhad ; S. Mehdi Hashemi ; Brendan D. McKay ; Maryam Tahmasbi
- 关键词：Cubic graph ; Ortho-radial grid ; Rectangular drawing ; Rectangular dual ; Rectangular-radial drawing
- 刊名：Computational Geometry
- 出版年：2010
- 出版时间：November 2010
- 年：2010
- 卷：43
- 期：9
- 页码：767-780
- 全文大小：308 K
文摘
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.