<div class="csl-bib-body">
<div class="csl-entry">Ganian, R., Nöllenburg, M., & Röder, S. (2024). Minimizing Switches in Cased Graph Drawings. In S. Felsner & K. Klein (Eds.), <i>32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)</i> (pp. 1–43). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.43</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/208539
-
dc.description.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
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
beyond planarity
en
dc.subject
complexity theory
en
dc.subject
crossings
en
dc.subject
non-planar drawings
en
dc.title
Minimizing Switches in Cased Graph Drawings
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.relation.publication
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
-
dc.contributor.affiliation
TU Wien, Austria
-
dc.relation.isbn
978-3-95977-343-0
-
dc.relation.issn
1868-8969
-
dc.description.startpage
1
-
dc.description.endpage
43
-
dc.relation.grantno
ICT22-029
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
-
tuw.container.volume
320
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
tuw.book.chapter
43
-
tuw.project.title
Parameterized Graph Drawing
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.4230/LIPIcs.GD.2024.43
-
dc.description.numberOfPages
43
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.author.orcid
0009-0005-5710-5975
-
tuw.editor.orcid
0000-0002-6150-1998
-
tuw.event.name
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
en
tuw.event.startdate
18-09-2024
-
tuw.event.enddate
20-09-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Vienna
-
tuw.event.country
AT
-
tuw.event.institution
TU Wien
-
tuw.event.presenter
Ganian, Robert
-
tuw.event.track
Multi Track
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
crisitem.project.funder
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
crisitem.project.grantno
ICT22-029
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
