Record link: 
http://hdl.handle.net/20.500.12708/57514
-
Title: 
Planar L-Drawings of Directed Graphs
-
Citation: 
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.), Graph Drawing and Network Visualization. GD 2018 (pp. 465–478). Springer. https://doi.org/10.1007/978-3-319-73915-1_36
-
Publisher DOI: 
10.1007/978-3-319-73915-1_36
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Chaplick, Steven 
Chimani, Markus 
Cornelsen, Sabine 
Da Lozzo, Giordano 
Nöllenburg, Martin 
Patrignani, Maurizio 
Tollis, Ioannis G. 
Wolff, Alexander 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Graph Drawing and Network Visualization. GD 2018 
-
ISBN: 
978-3-030-04414-5
-
Volume: 
11282
-
DOI of the book: 
10.1007/978-3-030-04414-5
-
Date (published): 
2018
-
Event name: 
26th International Symposium on Graph Drawing and Network Visualization (GD 2018) 
-
Event date: 
26-Sep-2018 - 28-Sep-2018
-
Event place: 
Barcelona, Spain
-
Number of Pages: 
14
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
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
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

240
checked on Nov 23, 2023

Google ScholarTM

Check