<div class="csl-bib-body">
<div class="csl-entry">Depian, T., Fink, S. D., Firbas, A., Ganian, R., & Nöllenburg, M. (2025). Pathways to Tractability for Geometric Thickness. In <i>SOFSEM 2025: Theory and Practice of Computer Science : 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20–23, 2025, Proceedings, Part I</i> (pp. 209–224). Springer. https://doi.org/10.1007/978-3-031-82670-2_16</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/220014
-
dc.description.abstract
We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible so that each part is crossing-free. Since the problem is NP-hard, we investigate its tractability through the lens of parameterized complexity. As our first set of contributions, we provide two fixed-parameter algorithms which utilize well-studied parameters of the input graph, notably the vertex cover and feedback edge numbers. Since parameterizing by the thickness itself does not yield tractability and the use of other structural parameters remains open due to general challenges identified in previous works, as our second set of contributions, we propose a different pathway to tractability for the problem: extension of partial solutions. In particular, we establish a full characterization of the problem’s parameterized complexity in the extension setting depending on whether we parameterize by the number of missing vertices, edges, or both.
en
dc.language.iso
en
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.subject
geometric thickness
en
dc.subject
parameterized complexity
en
dc.subject
vertex cover number
en
dc.title
Pathways to Tractability for Geometric Thickness
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.relation.isbn
978-3-031-82670-2
-
dc.relation.doi
10.1007/978-3-031-82670-2
-
dc.relation.issn
0302-9743
-
dc.description.startpage
209
-
dc.description.endpage
224
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
SOFSEM 2025: Theory and Practice of Computer Science : 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20–23, 2025, Proceedings, Part I
-
tuw.container.volume
15538
-
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.publication.orgunit
E056-13 - Fachbereich LogiCS
-
tuw.publisher.doi
10.1007/978-3-031-82670-2_16
-
dc.description.numberOfPages
16
-
tuw.author.orcid
0009-0003-7498-6271
-
tuw.author.orcid
0000-0002-2754-1195
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.event.name
50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2025)
en
tuw.event.startdate
20-01-2025
-
tuw.event.enddate
23-01-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Bratislava
-
tuw.event.country
SK
-
tuw.event.presenter
Depian, Thomas
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity