Options
Cubic plane graphs on a given point set
Publikationstyp
Conference Paper
Date Issued
2012-07
Sprache
English
Author(s)
TORE-URI
Start Page
201
End Page
208
Citation
28th Annual Symposuim on Computational Geometry (SCG 2012)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Association for Computing Machinery (ACM)
ISBN of container
978-1-4503-1299-8
Let P be a set of n ≥ 4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a cubic plane straight-line graph on P. No polynomial-time algorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-time algorithm; the algorithm is constructive and runs in time O(n 3). We also show which graph structure can be expected when there is a cubic plane graph on P; e. g., if P admits a 2-connected cubic plane graph, we show that P admits also a 2-connected cubic plane graph that contains the boundary cycle of P. The algorithm extends to checking P on admitting a 2-connected cubic plane graph.
Subjects
Cubic graphs
Planar embedding
Point set
DDC Class
600: Technology