Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions

A non-degenerate rectangular subdivision is a subdivision of a rectangle into a set of non-overlapping rectangles S, such that no four rectangles meet in a point. We consider a problem that Katz and colleagues call strong polychromatic four-colouring: colouring the vertices of the subdivision with four colours, such that each rectangle of S has all colours among its four corners. By considering the possible colouring patterns, we can give short proofs of colourability for subdivisions that are sliceable or one-sided. We also present techniques and observations for non-sliceable, two-sided subdivisions, for which the colourability question is still open.

keywords: Computational Geometry, Graphs Theory

Workshop or Poster (weakly reviewed)

Bettina Speckmann, Elena Mumford, Herman Haverkort, Jack Snoeyink, Maarten Löffler, Matthew O'Meara
Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions
Proc. 24th European Workshop on Computational Geometry
75–78, 2008

back to list