Four colouring the vertices of the triangulation of a polygon containing a hole

Graham M. Seed, D. E R Clark, Raffaella Ocone, Xiaoyan Y. Yang

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

Abstract

A simple linear-time algorithm is presented for four-colouring the vertices of a triangulation of a polygon containing a single hole. The algorithm consists of reducing a triangulation by the removal of both polygon and hole ear vertices, if any, followed by the removal of colour-isolated vertices until a 3-coloured tessellation remains. The triangulation is then re-built, using at most four colours. The paper concludes by recognising the similarity between the colouring of triangulations of polygons containing a hole and the colouring of bipartite and permutation graphs. © Springer-Verlag 2003.

Original languageEnglish
Title of host publicationComputational Science and Its Applications — ICCSA 2003
Subtitle of host publicationInternational Conference Montreal, Canada, May 18–21, 2003 Proceedings, Part III
Pages894-902
Number of pages9
Volume2669
ISBN (Electronic)978-3-540-44842-6
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
Volume2669
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Four colouring the vertices of the triangulation of a polygon containing a hole'. Together they form a unique fingerprint.

Cite this