3-Colorability of Pseudo-Triangulations

O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, A. Pilz, and B. Vogtenhuber

Abstract:

Deciding $3$-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 $3$-coloring always 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. $26^{th}$ European Workshop on Computational Geometry EuroCG '10, pages 21-24, Dortmund, Germany, 2010.