Rectangular-radial drawings of cubic plane graphs

Mahdieh Hasheminezhad; S. Mehdi Hashemi; Brendan D. McKay; Maryam Tahmasbi

doi:10.1016/j.comgeo.2010.06.001

Rectangular-radial drawings of cubic plane graphs

Mahdieh Hasheminezhad^*, S. Mehdi Hashemi, Brendan D. McKay, Maryam Tahmasbi

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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.

Original language	English
Pages (from-to)	767-780
Number of pages	14
Journal	Computational Geometry: Theory and Applications
Volume	43
Issue number	9
DOIs	https://doi.org/10.1016/j.comgeo.2010.06.001
Publication status	Published - Nov 2010

Access to Document

10.1016/j.comgeo.2010.06.001

Cite this

@article{5eca737fdc534cc6a50dfddb062f1422,

title = "Rectangular-radial drawings of cubic plane graphs",

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.",

keywords = "Cubic graph, Ortho-radial grid, Rectangular drawing, Rectangular dual, Rectangular-radial drawing",

author = "Mahdieh Hasheminezhad and Hashemi, {S. Mehdi} and McKay, {Brendan D.} and Maryam Tahmasbi",

year = "2010",

month = nov,

doi = "10.1016/j.comgeo.2010.06.001",

language = "English",

volume = "43",

pages = "767--780",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "9",

}

TY - JOUR

T1 - Rectangular-radial drawings of cubic plane graphs

AU - Hasheminezhad, Mahdieh

AU - Hashemi, S. Mehdi

AU - McKay, Brendan D.

AU - Tahmasbi, Maryam

PY - 2010/11

Y1 - 2010/11

N2 - 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.

AB - 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.

KW - Cubic graph

KW - Ortho-radial grid

KW - Rectangular drawing

KW - Rectangular dual

KW - Rectangular-radial drawing

UR - http://www.scopus.com/inward/record.url?scp=77954660079&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2010.06.001

DO - 10.1016/j.comgeo.2010.06.001

M3 - Article

SN - 0925-7721

VL - 43

SP - 767

EP - 780

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 9

ER -

Rectangular-radial drawings of cubic plane graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this