Geodesic
Removing Popular Faces in Curve Arrangements
Phoebe de Nooijer1 ; Soeren Terziadis2 ; Alexandra Weinberger3 ; Zuzana Masárová4 ; Tamara Mchedlidze1 ; Maarten Löffler1 ; Günter Rote5
1 Utrecht University
2 TU Eindhoven
3 FernUniversität in Hagen
4 IST Austria
5 FU Berlin
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023 , Tome 28 (2024) no. 2, pp. 47-82.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.v28i2.2988
Keywords: puzzle generation, curve arrangements, popular faces, fixed-parameter tractable (FPT)

Phoebe de Nooijer 1 ; Soeren Terziadis 2 ; Alexandra Weinberger 3 ; Zuzana Masárová 4 ; Tamara Mchedlidze 1 ; Maarten Löffler 1 ; Günter Rote 5

1 Utrecht University
2 TU Eindhoven
3 FernUniversität in Hagen
4 IST Austria
5 FU Berlin 
@article{JGAA_2024_28_2_a3,
     author = {Phoebe de Nooijer and Soeren Terziadis and Alexandra Weinberger and Zuzana Mas\'arov\'a and Tamara Mchedlidze and Maarten L\"offler and G\"unter Rote},
     title = {Removing {Popular} {Faces} in {Curve} {Arrangements}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {47--82},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2024},
     doi = {10.7155/jgaa.v28i2.2988},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2988/}
}
TY  - JOUR
AU  - Phoebe de Nooijer
AU  - Soeren Terziadis
AU  - Alexandra Weinberger
AU  - Zuzana Masárová
AU  - Tamara Mchedlidze
AU  - Maarten Löffler
AU  - Günter Rote
TI  - Removing Popular Faces in Curve Arrangements
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 47
EP  - 82
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2988/
DO  - 10.7155/jgaa.v28i2.2988
LA  - en
ID  - JGAA_2024_28_2_a3
ER  - 
%0 Journal Article
%A Phoebe de Nooijer
%A Soeren Terziadis
%A Alexandra Weinberger
%A Zuzana Masárová
%A Tamara Mchedlidze
%A Maarten Löffler
%A Günter Rote
%T Removing Popular Faces in Curve Arrangements
%J Journal of Graph Algorithms and Applications
%D 2024
%P 47-82
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2988/
%R 10.7155/jgaa.v28i2.2988
%G en
%F JGAA_2024_28_2_a3
Phoebe de Nooijer; Soeren Terziadis; Alexandra Weinberger; Zuzana Masárová; Tamara Mchedlidze; Maarten Löffler; Günter Rote. Removing Popular Faces in Curve Arrangements. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023
					, Tome 28 (2024) no. 2, pp. 47-82. doi : 10.7155/jgaa.v28i2.2988. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2988/

Cité par Sources :