Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

Florestan Brunck; Hsien Chih Chang; Maarten Löffler; Tim Ophelders; Lena Schlipf

doi:10.4230/LIPIcs.GD.2025.36

Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

Florestan Brunck^*
, Hsien Chih Chang^*
, Maarten Löffler^*
, Tim Ophelders^*
, Lena Schlipf^*

^*Corresponding author for this work

Sub Geometric Computing

University of Copenhagen
Dartmouth College
Utrecht University
TU
University of Tübingen

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

Abstract

We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).

Original language	English
Title of host publication	33rd International Symposium on Graph Drawing and Network Visualization, GD 2025
Editors	Vida Dujmovic, Fabrizio Montecchiani
Publisher	Dagstuhl Publishing
ISBN (Electronic)	9783959774031
DOIs	https://doi.org/10.4230/LIPIcs.GD.2025.36
Publication status	Published - 26 Nov 2025
Event	33rd International Symposium on Graph Drawing and Network Visualization, GD 2025 - Norrkoping, Sweden Duration: 24 Sept 2025 → 26 Sept 2025

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	357
ISSN (Print)	1868-8969

Conference

Conference	33rd International Symposium on Graph Drawing and Network Visualization, GD 2025
Country/Territory	Sweden
City	Norrkoping
Period	24/09/25 → 26/09/25

Bibliographical note

Publisher Copyright:
© Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf; licensed under Creative Commons License CC-BY 4.0.

Keywords

Curve Arrangements
Fixed-Parameter Tractability
NP-hardness
Puzzle Generation
Reconfiguration

Access to Document

10.4230/LIPIcs.GD.2025.36Licence: CC BY

Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular FacesFinal published version, 1.15 MBLicence: CC BY

Cite this

Brunck, F., Chang, H. C., Löffler, M., Ophelders, T., & Schlipf, L. (2025). Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. In V. Dujmovic, & F. Montecchiani (Eds.), 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025 Article 36 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 357). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.GD.2025.36

Brunck, Florestan ; Chang, Hsien Chih ; Löffler, Maarten et al. / Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025. editor / Vida Dujmovic ; Fabrizio Montecchiani. Dagstuhl Publishing, 2025. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{1b37012730bf46668108ddb97f1f211d,

title = "Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces",

abstract = "We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).",

keywords = "Curve Arrangements, Fixed-Parameter Tractability, NP-hardness, Puzzle Generation, Reconfiguration",

author = "Florestan Brunck and Chang, \{Hsien Chih\} and Maarten L{\"o}ffler and Tim Ophelders and Lena Schlipf",

note = "Publisher Copyright: {\textcopyright} Florestan Brunck, Hsien-Chih Chang, Maarten L{\"o}ffler, Tim Ophelders, and Lena Schlipf; licensed under Creative Commons License CC-BY 4.0.; 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025 ; Conference date: 24-09-2025 Through 26-09-2025",

year = "2025",

month = nov,

day = "26",

doi = "10.4230/LIPIcs.GD.2025.36",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl Publishing",

editor = "Vida Dujmovic and Fabrizio Montecchiani",

booktitle = "33rd International Symposium on Graph Drawing and Network Visualization, GD 2025",

}

Brunck, F, Chang, HC, Löffler, M, Ophelders, T & Schlipf, L 2025, Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. in V Dujmovic & F Montecchiani (eds), 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025., 36, Leibniz International Proceedings in Informatics, LIPIcs, vol. 357, Dagstuhl Publishing, 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025, Norrkoping, Sweden, 24/09/25. https://doi.org/10.4230/LIPIcs.GD.2025.36

Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. / Brunck, Florestan; Chang, Hsien Chih; Löffler, Maarten et al.
33rd International Symposium on Graph Drawing and Network Visualization, GD 2025. ed. / Vida Dujmovic; Fabrizio Montecchiani. Dagstuhl Publishing, 2025. 36 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 357).

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

TY - GEN

T1 - Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

AU - Brunck, Florestan

AU - Chang, Hsien Chih

AU - Löffler, Maarten

AU - Ophelders, Tim

AU - Schlipf, Lena

N1 - Publisher Copyright: © Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf; licensed under Creative Commons License CC-BY 4.0.

PY - 2025/11/26

Y1 - 2025/11/26

N2 - We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).

AB - We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).

KW - Curve Arrangements

KW - Fixed-Parameter Tractability

KW - NP-hardness

KW - Puzzle Generation

KW - Reconfiguration

UR - https://www.scopus.com/pages/publications/105031378403

U2 - 10.4230/LIPIcs.GD.2025.36

DO - 10.4230/LIPIcs.GD.2025.36

M3 - Conference contribution

AN - SCOPUS:105031378403

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025

A2 - Dujmovic, Vida

A2 - Montecchiani, Fabrizio

PB - Dagstuhl Publishing

T2 - 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025

Y2 - 24 September 2025 through 26 September 2025

ER -

Brunck F, Chang HC, Löffler M, Ophelders T, Schlipf L. Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. In Dujmovic V, Montecchiani F, editors, 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025. Dagstuhl Publishing. 2025. 36. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.GD.2025.36

Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this