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.

  pdf file
other papers about this subject
Last update: September 2, 2023.