<div class="csl-bib-body">
<div class="csl-entry">Nöllenburg, M., Sorge, M., Terziadis, S., Villedieu, A., Wu, H.-Y., & Wulms, J. (2023). Planarizing Graphs and Their Drawings by Vertex Splitting. In P. Angelini & R. von Haxleden (Eds.), <i>Graph Drawing and Network Visualization. GD 2022</i> (pp. 232–246). Springer. https://doi.org/10.1007/978-3-031-22203-0_17</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/190033
-
dc.description.abstract
The splitting number of a graph G= (V, E) is the minimum number of vertex splits required to turn G into a planar graph, where a vertex split removes a vertex v∈ V, introduces two new vertices v1, v2, and distributes the edges formerly incident to v among v1, v2. The splitting number problem is known to be NP-complete for abstract graphs and we provide a non-uniform fixed-parameter tractable (FPT) algorithm for this problem. We then shift focus to the splitting number of a given topological graph drawing in R2, where the new vertices resulting from vertex splits must be re-embedded into the existing drawing of the remaining graph. We show NP-completeness of this embedded splitting number problem, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.
en
dc.language.iso
en
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.subject
Parameterized complexity
en
dc.subject
Planarization
en
dc.subject
Vertex splitting
en
dc.title
Planarizing Graphs and Their Drawings by Vertex Splitting
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.editoraffiliation
John Cabot University, Italy
-
dc.contributor.editoraffiliation
Kiel University, Germany
-
dc.relation.isbn
978-3-031-22203-0
-
dc.relation.doi
10.1007/978-3-031-22203-0
-
dc.description.startpage
232
-
dc.description.endpage
246
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Graph Drawing and Network Visualization. GD 2022
-
tuw.container.volume
13764
-
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
E193-02 - Forschungsbereich Computer Graphics
-
tuw.publisher.doi
10.1007/978-3-031-22203-0_17
-
dc.description.numberOfPages
15
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.author.orcid
0000-0001-7394-3147
-
tuw.author.orcid
0000-0001-5161-3841
-
tuw.author.orcid
0000-0001-6196-8347
-
tuw.author.orcid
0000-0003-1028-0010
-
tuw.author.orcid
0000-0002-9314-8260
-
tuw.editor.orcid
0000-0002-7602-1524
-
tuw.event.name
International Symposium on Graph Drawing and Network Visualization (GD 2022)
en
tuw.event.startdate
13-09-2022
-
tuw.event.enddate
16-09-2022
-
tuw.event.online
Hybrid
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Tokyo
-
tuw.event.country
JP
-
tuw.event.institution
Tokyo Institute of Technology
-
tuw.event.presenter
Villedieu, Anaïs
-
tuw.event.track
Multi Track
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.fulltext
no Fulltext
-
item.grantfulltext
restricted
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
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
E193-02 - Forschungsbereich Computer Graphics
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.orcid
0000-0003-0454-3937
-
crisitem.author.orcid
0000-0001-5161-3841
-
crisitem.author.orcid
0000-0003-1028-0010
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E193 - Institut für Visual Computing and Human-Centered Technology