Removing Popular Faces in Curve Arrangements
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
Conference Proceedings (peer-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
Proc. 31st International Symposium on Graph Drawing
, 2023
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
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
CGWEEK: Workshop on Parameterized Algorithms for Geometric Problems
, 2023
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
