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 thateach rectangle of S has all colours among its four corners. By considering the possible colouring patterns, we can give short constructive proofs of colourabilityfor subdivisions that are sliceable or one-sided. We also present techniques and observations for nonsliceable, two-sided subdivisions.
|Publication status||Published - 2008|
|Event||24th European Workshop on Computational Geometry (EuroCG 2008) - Nancy, France|
Duration: 18 Mar 2008 → 20 Mar 2008
Conference number: 24
|Workshop||24th European Workshop on Computational Geometry (EuroCG 2008)|
|Period||18/03/08 → 20/03/08|