3-colorability of pseudo-triangulations
O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, A. Pilz, and
-colorability for general plane graphs is known to be an
NP-complete problem. However, for certain classes of plane graphs, like
triangulations, polynomial time algorithms exist. We consider the family of
pseudo-triangulations (a generalization of triangulations) and prove
NP-completeness for this class, even if the maximum face-degree is bounded to
four, or pointed pseudo-triangulations with maximum face degree five are
considered. As a complementary result, we show that for pointed
pseudo-triangulations with maximum face-degree four, a
exists and can be found in linear time.
Reference: O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, A. Pilz,
and B. Vogtenhuber.
3-colorability of pseudo-triangulations.
In Proc. European Workshop on Computational Geometry
EuroCG'10, pages 21-24, Dortmund, Germany, 2010.