2026-07-22T10:26:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25022 2026-02-09T07:53:44Z ddc:004 open_access

Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces Brunck, Florestan Chang, Hsien-Chih Löffler, Maarten Ophelders, Tim Schlipf, Lena Curve Arrangements Reconfiguration Curve Arrangements NP-hardness Fixed-Parameter Tractability Puzzle Generation 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florestan Brunck and Hsien-Chih Chang and Maarten Löffler and Tim Ophelders and Lena Schlipf 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.36 urn:nbn:de:0030-drops-250220 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode