Planar L-Drawings of directed graphs

DC ElementWertSprache
dc.contributor.authorChaplick, S.
dc.contributor.authorChimani, M.
dc.contributor.authorCornelsen, S.
dc.contributor.authorDa Lozzo, G.
dc.contributor.authorNöllenburg, M.
dc.contributor.authorPatrignani, M.
dc.contributor.authorTollis, I.G.
dc.contributor.authorWolff, A.
dc.contributor.editorMa, K.-L.
dc.contributor.editorFrati, F.
dc.date.accessioned2021-12-23T16:34:03Z-
dc.date.available2021-12-23T16:34:03Z-
dc.date.issued2018
dc.identifier.isbn9783319739144
dc.identifier.issn03029743
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17975-
dc.descriptionConference 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.abstractWe 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.sponsorshipMinistero 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.isoen
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectClustering algorithms
dc.subjectComputational complexity
dc.subjectDrawing (graphics)
dc.subjectVisualization, Linear-time algorithms
dc.subjectPlanar drawing, Directed graphs
dc.titlePlanar L-Drawings of directed graphs
dc.typeconference paper
dc.identifier.doi10.1007/978-3-319-73915-1_36
dc.identifier.scopus2-s2.0-85041830448
dc.identifier.urlhttps://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.volume10692 LNCS
dc.description.startpage465
dc.description.endpage478
dcterms.isPartOf.abbreviationLect. Notes Comput. Sci.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Zur Kurzanzeige

Seitenaufrufe

4
Letzte Woche
0
Letzter Monat
0
geprüft am 09.06.2024

Google ScholarTM

Prüfen

Altmetric