Removing Popular Faces in Curve Arrangements
Files
Publication date
2024-11-03
Authors
de Nooijer, Phoebe
Terziadis, Soeren
Weinberger, Alexandra
Masárová, Zuzana
Mchedlidze, Tamara
Löffler, Maarten
Rote, Günter
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
cc_by
Abstract
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 randomized FPT-time algorithm where the parameter is the number of popular faces.
Keywords
curve arrangements, fixed-parameter tractable (FPT), popular faces, puzzle generation, Theoretical Computer Science, General Computer Science, Computer Science Applications, Geometry and Topology, Computational Theory and Mathematics
Citation
de Nooijer, P, Terziadis, S, Weinberger, A, Masárová, Z, Mchedlidze, T, Löffler, M & Rote, G 2024, 'Removing Popular Faces in Curve Arrangements', Journal of Graph Algorithms and Applications, vol. 28, no. 2, pp. 47-82. https://doi.org/10.7155/jgaa.v28i2.2988