Record link: 
http://hdl.handle.net/20.500.12708/201368
-
Title: 
Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth
-
Citation: 
Jansen, B. M. P., Khazaliya, L., Kindermann, P., Liotta, G., Montecchiani, F., & Simonov, K. (2023). Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth. 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 (pp. 203–217). Springer. http://hdl.handle.net/20.500.12708/201368
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Jansen, Bart M. P. 
Khazaliya, Liana 
Kindermann, Philipp 
Liotta, Giuseppe 
Montecchiani, Fabrizio 
Simonov, Kirill 
-
Organisational Unit: 
E192 - Institut für Logic and Computation 
-
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: 
31st International Symposium on Graph Drawing and Network Visualizatio (GD 2023) 
en
Event date: 
20-Sep-2023 - 22-Sep-2023
-
Event place: 
Palermo, Italy
-
Number of Pages: 
15
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
Upward planarity; rectilinear planarity; parameterized complexity; Treewidth
en
Abstract: 
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known n O(tw)-time algorithms cannot be improved to run in time n o(tw) unless ETH fails
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Google ScholarTM

Check