Removing popular faces in curve arrangements

De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. Journal of Graph Algorithms and Applications. 28(2), 47–82.

Download
OA 2024_JourGraphAlgorithms_deNooijer.pdf 1.58 MB [Published Version]

Journal Article | Published | English

Scopus indexed
Author
De Nooijer, Phoebe; Terziadis, Soeren; Weinberger, Alexandra; Masárová, ZuzanaISTA ; Mchedlidze, Tamara; Löffler, Maarten; Rote, Günter

Corresponding author has ISTA affiliation

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 the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a randomized FPT-time algorithm where the parameter is the number of popular faces.
Publishing Year
Date Published
2024-11-03
Journal Title
Journal of Graph Algorithms and Applications
Publisher
Brown University
Acknowledgement
This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. has been supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035] and by the NWO Gravitation project NETWORKS under grant no. 024.002.003. Part of the work was done while A.W. was emplyed at Graz University of Technology. Preliminary versions of this work have been presented at the 38th European Workshop on Computational Geometry (EuroCG 2022) in Perugia [10] and at the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) in Isola delle Femmine [11].
Volume
28
Issue
2
Page
47-82
ISSN
IST-REx-ID

Cite this

De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. Journal of Graph Algorithms and Applications. 2024;28(2):47-82. doi:10.7155/jgaa.v28i2.2988
De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.v28i2.2988
De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” Journal of Graph Algorithms and Applications. Brown University, 2024. https://doi.org/10.7155/jgaa.v28i2.2988.
P. De Nooijer et al., “Removing popular faces in curve arrangements,” Journal of Graph Algorithms and Applications, vol. 28, no. 2. Brown University, pp. 47–82, 2024.
De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. Journal of Graph Algorithms and Applications. 28(2), 47–82.
De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” Journal of Graph Algorithms and Applications, vol. 28, no. 2, Brown University, 2024, pp. 47–82, doi:10.7155/jgaa.v28i2.2988.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2024-12-03
MD5 Checksum
be611da6f9d790dc980d6fb7283fe889


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2202.12175

Search this title in

Google Scholar