Planar L-Drawings of Bimodal Graphs

Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Da Lozzo, Giordano

Planar L-Drawings of Bimodal Graphs

Dateien

Angelini_2-uok0tutavxp20.pdfGröße: 888.92 KBDownloads: 9

Datum

2022

Autor:innen

Angelini, Patrizio

Chaplick, Steven

Cornelsen, Sabine

Da Lozzo, Giordano

URI (zitierfähiger Link)

http://nbn-resolving.de/urn:nbn:de:bsz:352-2-uok0tutavxp20

DOI (zitierfähiger Link)

https://doi.org/10.7155/jgaa.00596

Angaben zur Forschungsförderung

Deutsche Forschungsgemeinschaft (DFG): 50974019

Open Access-Veröffentlichung

Open Access Gold

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

Journal of Graph Algorithms and Applications. Brown University. 2022, 26(3), pp. 307-334. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00596

Zusammenfassung

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Bimodal graphs with 2-cycles admit a planar L-drawing if the underlying undirected graph with merged 2-cycles is a planar 3-tree. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding.

Fachgebiet (DDC)

004 Informatik

Schlagwörter

Computational Theory and Mathematics, Geometry and Topology, Computer Science Applications, General Computer Science, Theoretical Computer Science

Zitieren

ISO 690

ANGELINI, Patrizio, Steven CHAPLICK, Sabine CORNELSEN, Giordano DA LOZZO, 2022. Planar L-Drawings of Bimodal Graphs. In: Journal of Graph Algorithms and Applications. Brown University. 2022, 26(3), pp. 307-334. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00596

BibTex

@article{Angelini2022Plana-68524,
  year={2022},
  doi={10.7155/jgaa.00596},
  title={Planar L-Drawings of Bimodal Graphs},
  number={3},
  volume={26},
  journal={Journal of Graph Algorithms and Applications},
  pages={307--334},
  author={Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano}
}

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/68524">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-11-30T09:27:40Z</dc:date>
    <dc:contributor>Da Lozzo, Giordano</dc:contributor>
    <dc:language>eng</dc:language>
    <dc:creator>Da Lozzo, Giordano</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:creator>Angelini, Patrizio</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract>In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Bimodal graphs with 2-cycles admit a planar L-drawing if the underlying undirected graph with merged 2-cycles is a planar 3-tree. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding.</dcterms:abstract>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Chaplick, Steven</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-11-30T09:27:40Z</dcterms:available>
    <dcterms:issued>2022</dcterms:issued>
    <dc:contributor>Angelini, Patrizio</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/68524"/>
    <dc:contributor>Chaplick, Steven</dc:contributor>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/68524/1/Angelini_2-uok0tutavxp20.pdf"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/68524/1/Angelini_2-uok0tutavxp20.pdf"/>
    <dcterms:title>Planar L-Drawings of Bimodal Graphs</dcterms:title>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja

Begutachtet

Ja