Publikation: Planar L-Drawings of Directed Graphs
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
In this paper, we study drawings of directed graphs. We use the L-drawing standard where each edge is represented by a polygonal chain that consists of a vertical line segment incident to the source of the edge and a horizontal line segment incident to the target.
First, we consider planar L-drawings. 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. We also show how to decide in linear time whether there exists a planar L-drawing of a plane directed graph with a fixed assignment of the edges to the four sides (top, bottom, left, and right) of the vertices.
Second, we consider upward- (resp. upward-rightward-) planar L-drawings. We provide upper bounds on the maximum number of edges of graphs admitting such drawings. Moreover, we characterize the directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing as exactly those admitting an embedding supporting a bitonic (resp. monotonically decreasing) st-ordering.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
CHAPLICK, Steven, Markus CHIMANI, Sabine CORNELSEN, Giordano DA LOZZO, Martin NÖLLENBURG, Maurizio PATRIGNANI, IOANNIS G. TOLLIS, Alexander WOLFF, 2023. Planar L-Drawings of Directed Graphs. In: Computing in Geometry and Topology. Computing in Geometry and Topology. 2023, 2(1), 7. ISSN 2750-7823. Verfügbar unter: doi: 10.57717/cgt.v2i1.43BibTex
@article{Chaplick2023-11-12Plana-68529, year={2023}, doi={10.57717/cgt.v2i1.43}, title={Planar L-Drawings of Directed Graphs}, number={1}, volume={2}, issn={2750-7823}, journal={Computing in Geometry and Topology}, author={Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Ioannis G. Tollis and Wolff, Alexander}, note={Article Number: 7} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/68529"> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:contributor>Patrignani, Maurizio</dc:contributor> <dcterms:title>Planar L-Drawings of Directed Graphs</dcterms:title> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dcterms:issued>2023-11-12</dcterms:issued> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/68529/1/Chaplick_2-18z056q5maknx8.pdf"/> <dc:contributor>Chaplick, Steven</dc:contributor> <dc:creator>Chaplick, Steven</dc:creator> <dc:contributor>Nöllenburg, Martin</dc:contributor> <dc:contributor>Da Lozzo, Giordano</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-11-30T10:12:13Z</dc:date> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Patrignani, Maurizio</dc:creator> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Ioannis G. Tollis</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/68529/1/Chaplick_2-18z056q5maknx8.pdf"/> <dc:language>eng</dc:language> <dcterms:abstract>In this paper, we study drawings of directed graphs. We use the L-drawing standard where each edge is represented by a polygonal chain that consists of a vertical line segment incident to the source of the edge and a horizontal line segment incident to the target. First, we consider planar L-drawings. 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. We also show how to decide in linear time whether there exists a planar L-drawing of a plane directed graph with a fixed assignment of the edges to the four sides (top, bottom, left, and right) of the vertices. Second, we consider upward- (resp. upward-rightward-) planar L-drawings. We provide upper bounds on the maximum number of edges of graphs admitting such drawings. Moreover, we characterize the directed st-graphs admitting an upward- (resp. upward-rightward-) planar L-drawing as exactly those admitting an embedding supporting a bitonic (resp. monotonically decreasing) st-ordering.</dcterms:abstract> <dc:contributor>Chimani, Markus</dc:contributor> <dc:creator>Da Lozzo, Giordano</dc:creator> <dc:contributor>Ioannis G. Tollis</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/68529"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-11-30T10:12:13Z</dcterms:available> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:creator>Chimani, Markus</dc:creator> <dc:creator>Wolff, Alexander</dc:creator> <dc:creator>Nöllenburg, Martin</dc:creator> <dc:contributor>Wolff, Alexander</dc:contributor> </rdf:Description> </rdf:RDF>