Planar L-Drawings of Directed Graphs

Kurzanzeige
dc.contributor.authorChaplick, Steven
dc.contributor.authorChimani, Markus
dc.contributor.authorCornelsen, Sabine
dc.contributor.authorDa Lozzo, Giordano
dc.contributor.authorNöllenburg, Martin
dc.contributor.authorPatrignani, Maurizio
dc.contributor.authorIoannis G. Tollis
dc.contributor.authorWolff, Alexander
dc.date.accessioned2023-11-30T10:12:13Z
dc.date.available2023-11-30T10:12:13Z
dc.date.issued2023-11-12
dc.description.abstractIn 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.
dc.description.versionpublisheddeu
dc.identifier.doi10.57717/cgt.v2i1.43
dc.identifier.ppn1907292845
dc.identifier.urihttps://kops.uni-konstanz.de/handle/123456789/68529
dc.language.isoeng
dc.subject.ddc004
dc.titlePlanar L-Drawings of Directed Graphseng
dc.typeJOURNAL_ARTICLE
dspace.entity.typePublication
kops.citation.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}
}
kops.citation.iso690CHAPLICK, 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.43deu
kops.citation.iso690CHAPLICK, 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. Available under: doi: 10.57717/cgt.v2i1.43eng
kops.citation.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>
kops.description.funding{"first": "dfg", "second": "50974019"}
kops.description.openAccessopenaccessgold
kops.flag.isPeerReviewedunknown
kops.flag.knbibliographytrue
kops.identifier.nbnurn:nbn:de:bsz:352-2-18z056q5maknx8
kops.relation.dfgProjectID50974019
kops.sourcefieldComputing in Geometry and Topology. Computing in Geometry and Topology. 2023, <b>2</b>(1), 7. ISSN 2750-7823. Verfügbar unter: doi: 10.57717/cgt.v2i1.43deu
kops.sourcefield.plainComputing in Geometry and Topology. Computing in Geometry and Topology. 2023, 2(1), 7. ISSN 2750-7823. Verfügbar unter: doi: 10.57717/cgt.v2i1.43deu
kops.sourcefield.plainComputing in Geometry and Topology. Computing in Geometry and Topology. 2023, 2(1), 7. ISSN 2750-7823. Available under: doi: 10.57717/cgt.v2i1.43eng
relation.isAuthorOfPublicationab8dd64c-60a5-4662-9603-d40fd0e6c6f3
relation.isAuthorOfPublication.latestForDiscoveryab8dd64c-60a5-4662-9603-d40fd0e6c6f3
source.bibliographicInfo.articleNumber7
source.bibliographicInfo.issue1
source.bibliographicInfo.volume2
source.identifier.issn2750-7823
source.periodicalTitleComputing in Geometry and Topology
source.publisherComputing in Geometry and Topology
temp.internal.duplicatesitems/e07a9c59-9851-445d-b0a7-2d9316889a1f;true;Planar L-Drawings of Directed Graphs

Dateien

Originalbündel

Gerade angezeigt 1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
Chaplick_2-18z056q5maknx8.pdf
Größe:
823.56 KB
Format:
Adobe Portable Document Format
Chaplick_2-18z056q5maknx8.pdf
Chaplick_2-18z056q5maknx8.pdfGröße: 823.56 KBDownloads: 96

Sammlungen

Informatik und Informationswissenschaft: Publikationen