Minimizing Corners in Colored Rectilinear Grids

Abstract

Given a rectilinear grid G, in which cells are either assigned a single color, out of k possible colors, or remain white, can we color white grid cells of G to minimize the total number of corners of the resulting colored rectilinear polygons in G? We show how this problem relates to hypergraph visualization, prove that it is NP-hard even for k = 2, and present an exact dynamic programming algorithm. Together with a set of simple kernelization rules, this leads to an FPT-algorithm in the number of colored cells of the input. We additionally provide an XP-algorithm in the solution size, and a polynomial O (OP T)-approximation algorithm.