# Cubic Plane Graphs on a Given Point Set

*Discrete Structures and Algorithms (Seminar)*

*by Dr Jens Schmidt*

*Institution:*Max-Planck-Institut fur Informatik

*Date: Wed 3rd October 2012*

*Time: 1:00 PM*

*Location: Old Geology Theatre 2*

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