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
to appear 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. Editors:
Michael A. Bekos and Markus Chimani, Lecture Notes in Computer Science,
Springer-Verlag, 2023; 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
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: September 2, 2023.