School Seminars and Colloquia

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.