Removing Popular Faces in Curve Arrangements

Phoebe de Nooijer; Soeren Terziadis; Alexandra Weinberger; Zuzana Masárová; Tamara Mchedlidze; Maarten Löffler; Günter Rote

doi:10.7155/jgaa.v28i2.2988

Removing Popular Faces in Curve Arrangements

Authors

Phoebe de Nooijer Utrecht University
Soeren Terziadis TU Eindhoven
Alexandra Weinberger FernUniversität in Hagen
Zuzana Masárová IST Austria
Tamara Mchedlidze Utrecht University
Maarten Löffler Utrecht University
Günter Rote FU Berlin

DOI:

https://doi.org/10.7155/jgaa.v28i2.2988

Keywords:

puzzle generation, curve arrangements, popular faces, fixed-parameter tractable (FPT)

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.

Downloads

Download data is not yet available.

Downloads

Published

2024-11-03

How to Cite

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, 28(2), 47–82. https://doi.org/10.7155/jgaa.v28i2.2988