Título:
|
3-colorability of pseudo-triangulations
|
Autor/a:
|
Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Huemer, Clemens; Pilz, Alexander; Vogtenhuber, Birgit
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
Abstract:
|
Electronic version of an article published as International Journal of Computational Geometry & Applications, Vol. 25, No. 4 (2015) 283–298 DOI: 10.1142/S0218195915500168 © 2015 World Scientific Publishing Company. http://www.worldscientific.com/worldscinet/ijcga |
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. |
Materia(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística -Graph theory -pseudo-triangulation -3-colorability -face degree -Grafs, Teoria de |
Derechos:
|
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Tipo de documento:
|
Artículo - Versión presentada Artículo |
Compartir:
|
|