Record link: 
http://hdl.handle.net/20.500.12708/193211
-
Title: 
Fixed-Parameter Algorithms for Computing {RAC} Drawings of Graphs
en
Citation: 
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.), Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II (pp. 66–81). Springer. https://doi.org/10.1007/978-3-031-49275-4_5
-
Publisher DOI: 
10.1007/978-3-031-49275-4_5
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Brand, Cornelius 
Ganian, Robert 
Röder Sebastian 
Schager Florian 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Graph Drawing and Network Visualization : 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II 
-
ISBN: 
978-3-031-49274-7
-
Volume: 
14466
-
DOI of the book: 
10.1007/978-3-031-49275-4
-
Date (published): 
Sep-2023
-
Event name: 
Graph Drawing and Network Visualization - 31st International Symposium 
en
Event date: 
20-Sep-2023 - 22-Sep-2023
-
Event place: 
Palermo, Italy
-
Number of Pages: 
16
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
RAC drawing; Fixed-parameter tractability; Vertex cover number; feedback edge number
en
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
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)

200
checked on Feb 2, 2024

Google ScholarTM

Check