<div class="csl-bib-body">
<div class="csl-entry">Bhore, S., Ganian, R., Khazaliya, L., Montecchiani, F., & Nöllenburg, M. (2023). Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable. In E. Chambers & J. Gudmundsson (Eds.), <i>39th International Symposium on Computational Geometry</i> (pp. 1–16). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2023.18</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/188940
-
dc.description.abstract
The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well-known results providing efficient algorithms for fundamental representations such as planar and beyond-planar topological drawings. In this paper, we consider the extension problem for bend-minimal orthogonal drawings of planar graphs, which is among the most fundamental geometric graph drawing representations. While the problem was known to be NP-hard, it is natural to consider the case where only a small part of the graph is still to be drawn. Here, we establish the fixed-parameter tractability of the problem when parameterized by the size of the missing subgraph. Our algorithm is based on multiple novel ingredients which intertwine geometric and combinatorial arguments. These include the identification of a new graph representation of bend-equivalent regions for vertex placement in the plane, establishing a bound on the treewidth of this auxiliary graph, and a global point-grid that allows us to discretize the possible placement of bends and vertices into locally bounded subgrids for each of the above regions.
en
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
bend minimization
en
dc.subject
extension problems
en
dc.subject
orthogonal drawings
en
dc.subject
parameterized complexity
en
dc.title
Extending Orthogonal Planar Graph Drawings Is Fixed-Parameter Tractable
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Indian Institute of Technology Bombay, India
-
dc.contributor.affiliation
University of Perugia, Italy
-
dc.contributor.editoraffiliation
Saint Louis University, United States of America (the)
-
dc.contributor.editoraffiliation
University of Sydney, Australia
-
dc.relation.isbn
9783959772730
-
dc.relation.issn
1868-8969
-
dc.description.startpage
1
-
dc.description.endpage
16
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
39th International Symposium on Computational Geometry
-
tuw.container.volume
258
-
tuw.relation.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
tuw.relation.publisherplace
Dagstuhl
-
tuw.book.chapter
18
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.4230/LIPIcs.SoCG.2023.18
-
dc.description.numberOfPages
16
-
tuw.author.orcid
0000-0002-0543-8912
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.editor.orcid
0000-0001-8333-3676
-
tuw.editor.orcid
0000-0002-6778-7990
-
tuw.event.name
39th International Symposium on Computational Geometry
en
tuw.event.startdate
12-06-2023
-
tuw.event.enddate
15-06-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Dallas
-
tuw.event.country
US
-
tuw.event.presenter
Bhore, Sujoy
-
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.openairetype
conference paper
-
item.cerifentitytype
Publications
-
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
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity