Publikation:

Planar L-Drawings of Directed Graphs

Lade...
Vorschaubild

Dateien

Chaplick_2-18z056q5maknx8.pdf
Chaplick_2-18z056q5maknx8.pdfGröße: 823.56 KBDownloads: 6

Datum

2023

Autor:innen

Chaplick, Steven
Chimani, Markus
Da Lozzo, Giordano
Nöllenburg, Martin
Patrignani, Maurizio
Ioannis G. Tollis
Wolff, Alexander

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
oops

Angaben zur Forschungsförderung

Deutsche Forschungsgemeinschaft (DFG): 50974019

Projekt

Open Access-Veröffentlichung
Open Access Gold
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen 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.43

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)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CHAPLICK, 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.43
BibTex
@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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Unbekannt
Diese Publikation teilen