Planar L-Drawings of Directed Graphs

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

CHAPLICK, Steven, Markus CHIMANI, Sabine CORNELSEN, Giordano DA LOZZO, Martin NÖLLENBURG, Maurizio PATRIGNANI, Ioannis G. TOLLIS, Alexander WOLFF, 2018. Planar L-Drawings of Directed Graphs. Graph Drawing and Network Visualization : 25th International Symposium, GD 2017. Boston, MA, Sep 25, 2017 - Sep 27, 2017. In: FRATI, Fabrizio, ed., Kwan-Liu MA, ed.. Graph Drawing and Network Visualization : 25th International Symposium, GD 2017, Revised Selected Papers. Cham:Springer, pp. 465-478. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-73914-4. Available under: doi: 10.1007/978-3-319-73915-1_36

@inproceedings{Chaplick2018-01-21Plana-44792, title={Planar L-Drawings of Directed Graphs}, year={2018}, doi={10.1007/978-3-319-73915-1_36}, number={10692}, isbn={978-3-319-73914-4}, issn={0302-9743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Graph Drawing and Network Visualization : 25th International Symposium, GD 2017, Revised Selected Papers}, pages={465--478}, editor={Frati, Fabrizio and Ma, Kwan-Liu}, author={Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:creator>Wolff, Alexander</dc:creator> <dc:date rdf:datatype="">2019-01-31T13:40:47Z</dc:date> <dcterms:abstract xml:lang="eng">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.</dcterms:abstract> <dc:contributor>Da Lozzo, Giordano</dc:contributor> <dc:contributor>Patrignani, Maurizio</dc:contributor> <dc:creator>Chaplick, Steven</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:contributor>Wolff, Alexander</dc:contributor> <dcterms:available rdf:datatype="">2019-01-31T13:40:47Z</dcterms:available> <dcterms:title>Planar L-Drawings of Directed Graphs</dcterms:title> <dcterms:isPartOf rdf:resource=""/> <dc:creator>Chimani, Markus</dc:creator> <dc:contributor>Chaplick, Steven</dc:contributor> <dc:contributor>Tollis, Ioannis G.</dc:contributor> <dc:creator>Tollis, Ioannis G.</dc:creator> <dc:contributor>Nöllenburg, Martin</dc:contributor> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dc:creator>Patrignani, Maurizio</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:isPartOfCollection rdf:resource=""/> <dc:contributor>Chimani, Markus</dc:contributor> <bibo:uri rdf:resource=""/> <dc:language>eng</dc:language> <dc:creator>Da Lozzo, Giordano</dc:creator> <dcterms:issued>2018-01-21</dcterms:issued> <dc:creator>Nöllenburg, Martin</dc:creator> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account