<div class="csl-bib-body">
<div class="csl-entry">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 <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. 203–217). Springer. http://hdl.handle.net/20.500.12708/201368</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/201368
-
dc.description.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
dc.language.iso
en
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.subject
Upward planarity
en
dc.subject
rectilinear planarity
en
dc.subject
parameterized complexity
en
dc.subject
Treewidth
en
dc.title
Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth
-
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Universität Trier, Germany
-
dc.contributor.affiliation
University of Perugia, Italy
-
dc.contributor.affiliation
University of Perugia, Italy
-
dc.relation.isbn
978-3-031-49274-7
-
dc.relation.doi
10.1007/978-3-031-49275-4
-
dc.description.startpage
203
-
dc.description.endpage
217
-
dc.type.category
Full-Paper Contribution
-
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 - Institut für Logic and Computation
-
dc.description.numberOfPages
15
-
tuw.author.orcid
0009-0002-3012-7240
-
tuw.author.orcid
0000-0002-2886-9694
-
tuw.event.name
31st International Symposium on Graph Drawing and Network Visualizatio (GD 2023)
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
Khazaliya, Liana
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
item.grantfulltext
none
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
Universität Trier
-
crisitem.author.dept
University of Perugia
-
crisitem.author.dept
University of Perugia
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
