<div class="csl-bib-body">
<div class="csl-entry">Brand, C., Ganian, R., Röder Sebastian, & Schager Florian. (2023). Fixed-Parameter Algorithms for Computing {RAC} Drawings of Graphs. In M. A. Bekos & M. Chimani (Eds.), <i>Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II</i> (pp. 66–81). Springer. https://doi.org/10.1007/978-3-031-49275-4_5</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/193211
-
dc.description.abstract
In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly
, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph G with at most b bends (or determining that none exists) is fixed-parameter tractable parameterized by either the feedback edge number of G, or b plus the vertex cover number of G.
en
dc.language.iso
en
-
dc.subject
RAC drawing
en
dc.subject
Fixed-parameter tractability
en
dc.subject
Vertex cover number
en
dc.subject
feedback edge number
en
dc.title
Fixed-Parameter Algorithms for Computing {RAC} Drawings of Graphs
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.relation.publication
Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II
-
dc.contributor.affiliation
TU Wien, Austria
-
dc.contributor.affiliation
TU Wien, Austria
-
dc.contributor.editoraffiliation
University of Ioannina, Greece
-
dc.relation.isbn
978-3-031-49274-7
-
dc.relation.doi
10.1007/978-3-031-49275-4
-
dc.relation.issn
0302-9743
-
dc.description.startpage
66
-
dc.description.endpage
81
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II
-
tuw.container.volume
14466
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Cham
-
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.1007/978-3-031-49275-4_5
-
dc.description.numberOfPages
16
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.event.name
Graph Drawing and Network Visualization - 31st International Symposium
en
tuw.event.startdate
20-09-2023
-
tuw.event.enddate
22-09-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Palermo
-
tuw.event.country
IT
-
tuw.event.presenter
Ganian, Robert
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.cerifentitytype
Publications
-
item.openairetype
conference paper
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
