2026-07-23T04:54:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21327 2024-10-28T09:51:06Z ddc:004 open_access

Minimizing Switches in Cased Graph Drawings (Poster Abstract) Ganian, Robert Nöllenburg, Martin Röder, Sebastian beyond planarity complexity theory non-planar drawings crossings In cased drawings of graphs, edges are drawn in front of others in order to decrease the negative impact of crossings on readability. In this context, a switch on an edge is defined as two consecutive crossings, where the edge is drawn in the front at one crossing and behind another edge at the next crossing. We investigate the problem of minimizing the maximum number of switches on any edge - both in a fixed drawing as well as for non-embedded graphs. We resolve an open question by Eppstein, van Kreveld, Mumford, and Speckmann (2009) by establishing the NP-hardness of minimizing the number of switches in a fixed drawing, provide a fixed-parameter algorithm for this problem, and obtain a full characterization of the problem for non-embedded graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Ganian and Martin Nöllenburg and Sebastian Röder 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.43 urn:nbn:de:0030-drops-213271 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.43 eng https://creativecommons.org/licenses/by/4.0/legalcode