# Cubic Plane Graphs on a Given Point Set

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