Phoebe de Nooijer, Soeren Terziadis, Alexandra Weinberger, Zuzana
Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter
Rote:
1. Removing popular faces in curve arrangements
In: Graph Drawing and Network Visualization. GD 2023, Proceedings of the
31th International Symposium on Graph Drawing and Network Visualization,
Palermo, September 2023, Revised Selected Papers, Part II. Editors:
Michael A. Bekos and Markus Chimani, Lecture Notes in Computer Science,
14466, Springer-Verlag, 2023, pp. 18–33.
doi:10.1007/978-3-031-49275-4_2.
Full version in arXiv:2202.12175
[cs.CG]
→BibTeX
2. Removing popular faces in curve arrangements by inserting one more
curve
In Abstracts
of the 38th European Workshop on Computational Geometry (EuroCG 2022),
Perugia, March 14–16, 2022, Editors: Emilio Di Giacomo and Fabrizio
Montecchiani, pp. 38:1–38:8.
→BibTeX
3. Removing popular faces in curve arrangements
Journal of Graph Algorithms and
Applications 28, no. 2 (2024), pp. 47–82. Special
issue with selected papers from the Thirty-First International Symposium
on Graph Drawing and Network Visualization, GD 2023, doi:10.7155/jgaa.v28i2.2988
→BibTeX
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 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.
Last update: January 17, 2025.