Planar L-Drawings of directed graphs
| Autor(en): | Chaplick, S. Chimani, M. Cornelsen, S. Da Lozzo, G. Nöllenburg, M. Patrignani, M. Tollis, I.G. Wolff, A. |
Herausgeber: | Ma, K.-L. Frati, F. |
Stichwörter: | Clustering algorithms; Computational complexity; Drawing (graphics); Visualization, Linear-time algorithms; Planar drawing, Directed graphs | Erscheinungsdatum: | 2018 | Herausgeber: | Springer Verlag | Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Volumen: | 10692 LNCS | Startseite: | 465 | Seitenende: | 478 | Zusammenfassung: | 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. © Springer International Publishing AG 2018. |
Beschreibung: | Conference of 25th International Symposium on Graph Drawing and Network Visualization, GD 2017 ; Conference Date: 25 September 2017 Through 27 September 2017; Conference Code:210129 |
ISBN: | 9783319739144 | ISSN: | 03029743 | DOI: | 10.1007/978-3-319-73915-1_36 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85041830448&doi=10.1007%2f978-3-319-73915-1_36&partnerID=40&md5=74f308f028dbca75bd4260dd8d79ba62 |
Show full item record
