Removing Popular Faces in Curve Arrangements by Inserting one more Curve
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.
keywords: Computational Geometry, Fixed-Parameter Tractability, Graph Drawing, Graphs Theory, Puzzles
Workshop or Poster (weakly reviewed)
Alexandra Weinberger, Günter Rote, Maarten Löffler, Phoebe de Nooijer, Soeren Nickel, Tamara Mchedlidze, Zuzana Masárová
Removing Popular Faces in Curve Arrangements by Inserting one more Curve
Proc. 38th European Workshop on Computational Geometry
, 2022
Archived Publication (not reviewed)
Alexandra Weinberger, Günter Rote, Maarten Löffler, Phoebe de Nooijer, Soeren Nickel, Tamara Mchedlidze, Zuzana Masárová
Removing Popular Faces in Curve Arrangements by Inserting one more Curve
2202.12175, 2022
back to list