Abstract
We give the first polynomial-time algorithm for deciding whether there is a cubic plane straight-line graph on a given finite point set in general position in the plane. If such a plane graph exists, it is found in cubic time.
We give the first polynomial-time algorithm for deciding whether there is a cubic plane straight-line graph on a given finite point set in general position in the plane. If such a plane graph exists, it is found in cubic time.