Minimizing Corners in Colored Rectilinear Grids

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 \(\mathcal {O}(OPT)\) -approximation algorithm.