Cubic Plane Graphs on a Given Point Set
by Dr Jens Schmidt
Abstract: Let P be a set of \(n \geq 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. 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 \(O(n^3)\) time. This is joint-work with Pavel Valtr.