Removing Popular Faces in Curve Arrangements

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

doi:10.7155/jgaa.v28i2.2988

Removing Popular Faces in Curve Arrangements

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

Research output: Contribution to journal › Article › 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 randomized FPT-time algorithm where the parameter is the number of popular faces.

Original language	English
Pages (from-to)	47-82
Number of pages	36
Journal	Journal of Graph Algorithms and Applications
Volume	28
Issue number	2
DOIs	https://doi.org/10.7155/jgaa.v28i2.2988
Publication status	Published - 3 Nov 2024

Bibliographical note

Publisher Copyright:
© 2024, Brown University. All rights reserved.

Keywords

curve arrangements
fixed-parameter tractable (FPT)
popular faces
puzzle generation

Access to Document

10.7155/jgaa.v28i2.2988Licence: CC BY

674Final published version, 1.51 MBLicence: CC BY

Cite this

@article{cbd18f9cbc924b17adae30f7d7cd05b2,

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 randomized FPT-time algorithm where the parameter is the number of popular faces.",

keywords = "curve arrangements, fixed-parameter tractable (FPT), popular faces, puzzle generation",

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

year = "2024",

month = nov,

day = "3",

doi = "10.7155/jgaa.v28i2.2988",

language = "English",

volume = "28",

pages = "47--82",

journal = "Journal of Graph Algorithms and Applications",

issn = "1526-1719",

publisher = "Brown University",

number = "2",

}

TY - JOUR

T1 - Removing Popular Faces in Curve Arrangements

AU - de Nooijer, Phoebe

AU - Terziadis, Soeren

AU - Weinberger, Alexandra

AU - Masárová, Zuzana

AU - Mchedlidze, Tamara

AU - Löffler, Maarten

AU - Rote, Günter

PY - 2024/11/3

Y1 - 2024/11/3

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 randomized FPT-time algorithm where the parameter is 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 randomized FPT-time algorithm where the parameter is the number of popular faces.

KW - curve arrangements

KW - fixed-parameter tractable (FPT)

KW - popular faces

KW - puzzle generation

UR - http://www.scopus.com/inward/record.url?scp=85209910961&partnerID=8YFLogxK

U2 - 10.7155/jgaa.v28i2.2988

DO - 10.7155/jgaa.v28i2.2988

M3 - Article

AN - SCOPUS:85209910961

SN - 1526-1719

VL - 28

SP - 47

EP - 82

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 2

ER -

Removing Popular Faces in Curve Arrangements

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this