2023/11/23 by Thomas Depian, Depian, Thomas, Alexander Dobler +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2311.14134
openalex publication_date 2023/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(OPT)-approximation algorithm.