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

doi:10.1007/3-540-44842-X_91

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 proceeding › Chapter (peer-reviewed) › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	Computational Science and Its Applications — ICCSA 2003
Subtitle of host publication	International Conference Montreal, Canada, May 18–21, 2003 Proceedings, Part III
Pages	894-902
Number of pages	9
Volume	2669
ISBN (Electronic)	978-3-540-44842-6
DOIs	https://doi.org/10.1007/3-540-44842-X_91
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science
Volume	2669
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-44842-X_91

Cite this

Seed, G. M., Clark, D. E. R., Ocone, R., & Yang, X. Y. (2003). Four colouring the vertices of the triangulation of a polygon containing a hole. In Computational Science and Its Applications — ICCSA 2003: International Conference Montreal, Canada, May 18–21, 2003 Proceedings, Part III (Vol. 2669, pp. 894-902). (Lecture Notes in Computer Science; Vol. 2669). https://doi.org/10.1007/3-540-44842-X_91

@inbook{68577da67fa642bd8528b5537f6bdbde,

title = "Four colouring the vertices of the triangulation of a polygon containing a hole",

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. {\textcopyright} Springer-Verlag 2003.",

author = "Seed, {Graham M.} and Clark, {D. E R} and Raffaella Ocone and Yang, {Xiaoyan Y.}",

year = "2003",

doi = "10.1007/3-540-44842-X_91",

language = "English",

isbn = "978-3-540-40156-8",

volume = "2669",

series = "Lecture Notes in Computer Science",

pages = "894--902",

booktitle = "Computational Science and Its Applications — ICCSA 2003",

}

Seed, GM, Clark, DER, Ocone, R & Yang, XY 2003, Four colouring the vertices of the triangulation of a polygon containing a hole. in Computational Science and Its Applications — ICCSA 2003: International Conference Montreal, Canada, May 18–21, 2003 Proceedings, Part III. vol. 2669, Lecture Notes in Computer Science, vol. 2669, pp. 894-902. https://doi.org/10.1007/3-540-44842-X_91

Four colouring the vertices of the triangulation of a polygon containing a hole. / Seed, Graham M.; Clark, D. E R; Ocone, Raffaella et al.
Computational Science and Its Applications — ICCSA 2003: International Conference Montreal, Canada, May 18–21, 2003 Proceedings, Part III. Vol. 2669 2003. p. 894-902 (Lecture Notes in Computer Science; Vol. 2669).

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

TY - CHAP

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

AU - Seed, Graham M.

AU - Clark, D. E R

AU - Ocone, Raffaella

AU - Yang, Xiaoyan Y.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35248841063&partnerID=8YFLogxK

U2 - 10.1007/3-540-44842-X_91

DO - 10.1007/3-540-44842-X_91

M3 - Chapter (peer-reviewed)

SN - 978-3-540-40156-8

VL - 2669

T3 - Lecture Notes in Computer Science

SP - 894

EP - 902

BT - Computational Science and Its Applications — ICCSA 2003

ER -

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

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this