Phoebe de Nooijer, Soeren Nickel, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote:

Removing popular faces in curve arrangements by inserting one more curve

In: Abstracts of the 38th European Workshop on Computational Geometry (EuroCG 2022), Perugia, March 2022, pp. 38:1–38:8. arXiv:2202.12175 [cs.CG],  →BibTeX


A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate popular faces in an arrangement by inserting a single additional curve. This turns out to be already NP-hard; however, we present a probabilistic FPT-approach in the number of such faces.

other papers about this subject
Last update: April 21, 2022.