Planar L-Drawings of directed graphs
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Chaplick, S. | |
dc.contributor.author | Chimani, M. | |
dc.contributor.author | Cornelsen, S. | |
dc.contributor.author | Da Lozzo, G. | |
dc.contributor.author | Nöllenburg, M. | |
dc.contributor.author | Patrignani, M. | |
dc.contributor.author | Tollis, I.G. | |
dc.contributor.author | Wolff, A. | |
dc.contributor.editor | Ma, K.-L. | |
dc.contributor.editor | Frati, F. | |
dc.date.accessioned | 2021-12-23T16:34:03Z | - |
dc.date.available | 2021-12-23T16:34:03Z | - |
dc.date.issued | 2018 | |
dc.identifier.isbn | 9783319739144 | |
dc.identifier.issn | 03029743 | |
dc.identifier.uri | https://osnascholar.ub.uni-osnabrueck.de/handle/unios/17975 | - |
dc.description | 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 | |
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. © Springer International Publishing AG 2018. | |
dc.description.sponsorship | Ministero dell'Istruzione, dell'Università e della RicercaMinistero dell'Istruzione, dell'Università e della Ricerca,MIUR,20157EFM5C 001; This research was initiated at the Bertinoro Workshop on Graph Drawing 2017. This article reports on work supported by the U.S. Defense Advanced Research Projects Agency (DARPA) under agreement no. AFRL FA8750-15-2-0092. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense or the U.S. Government. This research was also partially supported by MIUR project “MODE – MOrphing graph Drawings Efficiently”, prot. 20157EFM5C 001.; | |
dc.language.iso | en | |
dc.publisher | Springer Verlag | |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
dc.subject | Clustering algorithms | |
dc.subject | Computational complexity | |
dc.subject | Drawing (graphics) | |
dc.subject | Visualization, Linear-time algorithms | |
dc.subject | Planar drawing, Directed graphs | |
dc.title | Planar L-Drawings of directed graphs | |
dc.type | conference paper | |
dc.identifier.doi | 10.1007/978-3-319-73915-1_36 | |
dc.identifier.scopus | 2-s2.0-85041830448 | |
dc.identifier.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 | |
dc.description.volume | 10692 LNCS | |
dc.description.startpage | 465 | |
dc.description.endpage | 478 | |
dcterms.isPartOf.abbreviation | Lect. Notes Comput. Sci. | |
crisitem.author.orcid | 0000-0002-4681-5550 | - |
crisitem.author.netid | ChMa572 | - |
Seitenaufrufe
4
Letzte Woche
0
0
Letzter Monat
0
0
geprüft am 09.06.2024