Record link: 
http://hdl.handle.net/20.500.12708/208539
-
Title: 
Minimizing Switches in Cased Graph Drawings
en
Citation: 
Ganian, R., Nöllenburg, M., & Röder, S. (2024). Minimizing Switches in Cased Graph Drawings. In S. Felsner & K. Klein (Eds.), 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) (pp. 1–43). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.43
-
Publisher DOI: 
10.4230/LIPIcs.GD.2024.43
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Ganian, Robert 
Nöllenburg, Martin 
Röder, Sebastian 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) 
-
ISBN: 
978-3-95977-343-0
-
Volume: 
320
-
Date (published): 
28-Oct-2024
-
Event name: 
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) 
en
Event date: 
18-Sep-2024 - 20-Sep-2024
-
Event place: 
Vienna, Austria
-
Number of Pages: 
43
-
Publisher: 
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Peer reviewed: 
Yes
-
Keywords: 
beyond planarity; complexity theory; crossings; non-planar drawings
en
Abstract: 
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.
en
Project title: 
Parameterized Graph Drawing: ICT22-029 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds) 
-
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

125
checked on Jan 13, 2025

Google ScholarTM

Check