{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:05:44Z","timestamp":1774591544283,"version":"3.50.1"},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0218195915500168","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T03:32:48Z","timestamp":1454297568000},"page":"283-298","source":"Crossref","is-referenced-by-count":1,"title":["3-Colorability of Pseudo-Triangulations"],"prefix":"10.1142","volume":"25","author":[{"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[{"name":"Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b\/II, Graz, Austria"}]},{"given":"Franz","family":"Aurenhammer","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Computer Science, Graz University of Technology, Inffeldgasse 16b\/I, Graz, Austria"}]},{"given":"Thomas","family":"Hackl","sequence":"additional","affiliation":[{"name":"Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b\/II, Graz, Austria"}]},{"given":"Clemens","family":"Huemer","sequence":"additional","affiliation":[{"name":"Departament de Matem\u00e0tica Alicada IV, Universitat Polit\u00e8cnica de Catalunya BarcelonaTech, C. Esteve Terradas 5, Castelldefels, Spain"}]},{"given":"Alexander","family":"Pilz","sequence":"additional","affiliation":[{"name":"Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b\/II, Graz, Austria"}]},{"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[{"name":"Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b\/II, Graz, Austria"}]}],"member":"219","published-online":{"date-parts":[[2016,1,27]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702411368"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.07.002"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195914600036"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-004-0574-z"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.07.003"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.09.045"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08807"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70391-1"},{"key":"p_14","first-page":"19","volume":"5","author":"Stockmeyer L.","year":"1973","journal-title":"Planar 3-colorability is polynomial complete, SIGACT News"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195915500168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:53:21Z","timestamp":1565186001000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195915500168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2016,1,27]]},"published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1142\/S0218195915500168"],"URL":"https:\/\/doi.org\/10.1142\/s0218195915500168","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}