### 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 | |

Publication status | Published - 2003 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 2669 |

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

*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