<div class="csl-bib-body">
<div class="csl-entry">Hummel, M., Klute, F., Nickel, S., & Nöllenburg, M. (2019). Maximizing Ink in Partial Edge Drawings of k-plane Graphs. In <i>Graph Drawing and Network Visualization. GD 2019</i> (pp. 323–336). Springer. https://doi.org/10.1007/978-3-030-35802-0_25</div>
</div>
-
dc.identifier.isbn
9783030358013
-
dc.identifier.isbn
9783030358020
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/57991
-
dc.description.abstract
Partial edge drawing (PED) is a drawing style for non-planar
graphs, in which edges are drawn only partially as pairs of opposing
stubs on the respective end-vertices. In a PED, by erasing the central
parts of edges, all edge crossings and the resulting visual clutter are
hidden in the undrawn parts of the edges. In symmetric partial edge
drawings (SPEDs), the two stubs of each edge are required to have the
same length. It is known that maximizing the ink (or the total stub
length) when transforming a straight-line graph drawing with crossings
into a SPED is tractable for 2-plane input drawings, but NP-hard for
unrestricted inputs. We show that the problem remains NP-hard even for
3-plane input drawings and establish NP-hardness of ink maximization
for PEDs of 4-plane graphs. Yet, for k-plane input drawings whose edge
intersection graph forms a collection of trees or, more generally, whose
intersection graph has bounded treewidth, we present efficient algorithms
for computing maximum-ink PEDs and SPEDs. We implemented the
treewidth-based algorithms and show a brief experimental evaluation.
en
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.title
Maximizing Ink in Partial Edge Drawings of k-plane Graphs
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.issn
0302-9743
-
dc.description.startpage
323
-
dc.description.endpage
336
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Graph Drawing and Network Visualization. GD 2019
-
tuw.container.volume
11904
-
tuw.peerreviewed
true
-
tuw.book.ispartofseries
Lecture Notes in Computer Science
-
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.publisher.doi
10.1007/978-3-030-35802-0_25
-
dc.description.numberOfPages
14
-
tuw.author.orcid
0000-0002-1780-6110
-
tuw.author.orcid
0000-0002-7791-3604
-
tuw.author.orcid
0000-0001-5161-3841
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.event.name
International Symposium on Graph Drawing and Network Visualization (GD 2019)
-
tuw.event.startdate
17-09-2019
-
tuw.event.enddate
20-09-2019
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Prag
-
tuw.event.country
CZ
-
tuw.event.presenter
Klute, Fabian
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.facultyfocus
Logic and Computation (LC)
de
wb.facultyfocus
Logic and Computation (LC)
en
wb.facultyfocus.faculty
E180
-
wb.presentation.type
science to science/art to art
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.grantfulltext
restricted
-
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