Cubic plane graphs on a given point set

Publikationstyp
Conference Paper
Date Issued
2012-07
Sprache
English
Author(s)
Schmidt, Jens M.  orcid-logo
Valtr, Pavel  
TORE-URI
http://hdl.handle.net/11420/7632
Start Page
201
End Page
208
Citation
SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry pp 201–208
Contribution to Conference
28th Annual Symposuim on Computational Geometry (SCG 2012)  
Publisher DOI
10.1145/2261250.2261281
Scopus ID
2-s2.0-84863931555
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