Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions

Herman Haverkort; Maarten Löffler; Elena Mumford; Jack Snoeyink; Bettina Speckmann; Matthew O'Meara

Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions

Herman Haverkort, Maarten Löffler, Elena Mumford, Jack Snoeyink, Bettina Speckmann, Matthew O'Meara

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

Abstract

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.

Original language	English
Title of host publication	Proc. 24th European Workshop on Computational Geometry
Pages	75-78
Number of pages	4
Publication status	Published - 2008

Keywords

CG, GRAPH

Cite this

@inproceedings{c54e3ac06956439586127075e83c2089,

title = "Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions",

abstract = "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 = "CG, GRAPH",

author = "Herman Haverkort and Maarten L{\"o}ffler and Elena Mumford and Jack Snoeyink and Bettina Speckmann and Matthew O'Meara",

year = "2008",

language = "English",

pages = "75--78",

booktitle = "Proc. 24th European Workshop on Computational Geometry",

}

TY - GEN

T1 - Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions

AU - Haverkort, Herman

AU - Löffler, Maarten

AU - Mumford, Elena

AU - Snoeyink, Jack

AU - Speckmann, Bettina

AU - O'Meara, Matthew

PY - 2008

Y1 - 2008

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

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

KW - CG, GRAPH

M3 - Conference contribution

SP - 75

EP - 78

BT - Proc. 24th European Workshop on Computational Geometry

ER -

Colour Patterns for Polychromatic Four-colouring of Rectangular Subdivisions

Abstract

Keywords

Fingerprint

Cite this