3-Colorability of Pseudo-Triangulations

DOI10.1142/S0218195915500168zbMath1352.68091OpenAlexW2188476072WikidataQ61732470 ScholiaQ61732470MaRDI QIDQ2792798

Oswin Aichholzer, Clemens Huemer, Franz Aurenhammer, Birgit Vogtenhuber, Alexander Pilz, Thomas Hackl

Publication date: 14 March 2016

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195915500168

zbMATH Keywords

3-colorabilitypseudo-triangulationface degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On 3-colouring of graphs with short faces and bounded maximum vertex degree

Cites Work

• Colorability of planar graphs with isolated nontriangular faces
• Combinatorial pseudo-triangulations
• Planar minimally rigid graphs and pseudo-triangulations
• Matching edges and faces in polygonal partitions
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• FLIPS IN COMBINATORIAL POINTED PSEUDO-TRIANGULATIONS WITH FACE DEGREE AT MOST FOUR

This page was built for publication: 3-Colorability of Pseudo-Triangulations