Back to Search
Start Over
3-Colorability of Pseudo-Triangulations.
- Source :
-
International Journal of Computational Geometry & Applications . Dec2015, Vol. 25 Issue 4, p283-298. 16p. - Publication Year :
- 2015
-
Abstract
- Deciding 3-colorability for general plane graphs is known to be an NP-complete problem. However, for certain families of graphs, like triangulations, polynomial time algorithms exist. We consider the family of pseudo-triangulations, which are a generalization of triangulations, and prove NP-completeness for this class. This result also holds if we bound their face degree to four, or exclusively consider pointed pseudo-triangulations with maximum face degree five. In contrast to these completeness results, we show that pointed pseudo-triangulations with maximum face degree four are always 3-colorable. An according 3-coloring can be found in linear time. Some complexity results relating to the rank of pseudo-triangulations are also given. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 25
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 112640730
- Full Text :
- https://doi.org/10.1142/S0218195915500168