Autor:	de Nooijer, Phoebe, Terziadis, Soeren, Weinberger, Alexandra, Masárová, Zuzana, Mchedlidze, Tamara, Löffler, Maarten, Rote, Günter
Rok vydání:	2022
Předmět:	Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	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 the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces. Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2202.12175 Zobrazit plný text záznamu View this record from Arxiv