Removing Popular Faces in Curve Arrangements

Phoebe de Nooijer; Soeren Nickel; Alexandra Weinberger; Zuzana Masárová; Tamara Mchedlidze; Maarten Löffler; Günter Rote

Removing Popular Faces in Curve Arrangements

Phoebe de Nooijer, Soeren Nickel, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, Günter Rote

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 probabilistic FPT-approach in the number of popular faces.

Original language	English
Title of host publication	Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)
Publication status	Published - 2023

Keywords

CG
GRAPH
GD
PUZ
FPT

Cite this

@inproceedings{358a283a6a774894afa70ae853c6ed45,

title = "Removing Popular Faces in Curve Arrangements",

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 probabilistic FPT-approach in the number of popular faces.",

keywords = "CG, GRAPH, GD, PUZ, FPT",

author = "{de Nooijer}, Phoebe and Soeren Nickel and Alexandra Weinberger and Zuzana Mas{\'a}rov{\'a} and Tamara Mchedlidze and Maarten L{\"o}ffler and G{\"u}nter Rote",

year = "2023",

language = "English",

booktitle = "Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)",

}

TY - GEN

T1 - Removing Popular Faces in Curve Arrangements

AU - de Nooijer, Phoebe

AU - Nickel, Soeren

AU - Weinberger, Alexandra

AU - Masárová, Zuzana

AU - Mchedlidze, Tamara

AU - Löffler, Maarten

AU - Rote, Günter

PY - 2023

Y1 - 2023

N2 - 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 probabilistic FPT-approach in the number of popular faces.

AB - 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 probabilistic FPT-approach in the number of popular faces.

KW - CG

KW - GRAPH

KW - GD

KW - PUZ

KW - FPT

M3 - Conference contribution

BT - Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

ER -

Removing Popular Faces in Curve Arrangements

Abstract

Keywords

Fingerprint

Cite this