Cubic plane graphs on a given point set (Q5891915)

Let \(P\) be a set of \(n\geq 4\) points in the plane which does not contain three points on a line and such that \(n\) is even. The authors study the question whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on \(P\). Relying on the reduction to the existence of certain diagonals of the boundary cycle of the convex hull of \(P\), they develop a polynomial-time algorithm which checks for 2-connected cubic plane graphs. It is constructive and runs in time \(O(n^3)\). They also explore the graph structure that can be expected when there is a cubic plane graph on \(P\). For example, they show that a 2-connected cubic plane graph on \(P\) implies a 2-connected cubic plane graph on \(P\) which includes the boundary cycle of \(P\). They finally extend the afore-mentioned algorithm to test for arbitrary cubic plane graphs in time \(O(n^3)\).