<div class="csl-bib-body">
<div class="csl-entry">Chaplick, S., Chimani, M., Cornelsen, S., Da Lozzo, G., Nöllenburg, M., Patrignani, M., Tollis, I. G., & Wolff, A. (2018). Planar L-Drawings of Directed Graphs. In F. Frati & K.-L. Ma (Eds.), <i>Graph Drawing and Network Visualization. GD 2018</i> (pp. 465–478). Springer. https://doi.org/10.1007/978-3-319-73915-1_36</div>
</div>
-
dc.identifier.isbn
9783319739151
-
dc.identifier.isbn
9783319739144
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/57514
-
dc.description.abstract
We study planar drawings of directed graphs in the L-drawing standard. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. Motivated by this result, we focus on upward-planar L-drawings. We show that directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing are exactly those admitting a bitonic (resp. monotonically increasing) st-ordering. We give a linear-time algorithm that computes a bitonic (resp. monotonically increasing) st-ordering of a planar st-graph or reports that there exists none.
en
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.title
Planar L-Drawings of Directed Graphs
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.isbn
978-3-030-04414-5
-
dc.relation.doi
10.1007/978-3-030-04414-5
-
dc.relation.issn
0302-9743
-
dc.description.startpage
465
-
dc.description.endpage
478
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Graph Drawing and Network Visualization. GD 2018
-
tuw.container.volume
11282
-
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-319-73915-1_36
-
dc.description.numberOfPages
14
-
tuw.author.orcid
0000-0001-5872-718X
-
tuw.event.name
26th International Symposium on Graph Drawing and Network Visualization (GD 2018)
-
tuw.event.startdate
26-09-2018
-
tuw.event.enddate
28-09-2018
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Barcelona
-
tuw.event.country
ES
-
tuw.event.presenter
Nöllenburg, Martin
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
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.fulltext
no Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
crisitem.author.dept
Maastricht University, The Netherlands
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen
-
crisitem.author.dept
Universität Konstanz, Germany
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity