The Painter's Problem: Covering a Grid with Colored Connected Polygons.

van Goethem, Arthur and Kostitsyna, Irina and van Kreveld, Marc and Meulemans, Wouter and Sondag, Max and Wulms, Jules (2017) The Painter's Problem: Covering a Grid with Colored Connected Polygons. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 492-505(Official URL: https://doi.org/10.1007/978-3-319-73915-1_38).

Full text not available from this repository.

Abstract

Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors χ. Each cell s in the grid is assigned a subset of colors χs⊆χ and should be partitioned such that for each color c∈χs at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where χ={red,blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.

Item Type: Conference Paper
Classifications: P Styles > P.420 Hyper
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1626

Actions (login required)

View Item View Item