On Upward-Planar L-Drawings of Graphs

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2022
Autor:innen
Angelini, Patrizio
Chaplick, Steven
Da Lozzo, Giordano
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
Projekt
Open Access-Veröffentlichung
Open Access Bookpart
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
SZEIDER, Stefan, ed., Robert GANIAN, ed., Alexandra SILVA, ed.. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Wadern: Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 2022, pp. 10:1-10:15. Leibniz International Proceedings in Informatics (LIPIcs). 241. eISSN 1868-8969. ISBN 978-3-95977-256-3. Available under: doi: 10.4230/LIPIcs.MFCS.2022.10
Zusammenfassung

In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of e and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but the DAG is biconnected and series-parallel.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), 22. Aug. 2022 - 26. Aug. 2022, Vienna, Austria
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690ANGELINI, Patrizio, Steven CHAPLICK, Sabine CORNELSEN, Giordano DA LOZZO, 2022. On Upward-Planar L-Drawings of Graphs. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Vienna, Austria, 22. Aug. 2022 - 26. Aug. 2022. In: SZEIDER, Stefan, ed., Robert GANIAN, ed., Alexandra SILVA, ed.. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Wadern: Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 2022, pp. 10:1-10:15. Leibniz International Proceedings in Informatics (LIPIcs). 241. eISSN 1868-8969. ISBN 978-3-95977-256-3. Available under: doi: 10.4230/LIPIcs.MFCS.2022.10
BibTex
@inproceedings{Angelini2022Upwar-68525,
  year={2022},
  doi={10.4230/LIPIcs.MFCS.2022.10},
  title={On Upward-Planar L-Drawings of Graphs},
  number={241},
  isbn={978-3-95977-256-3},
  publisher={Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik},
  address={Wadern},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  booktitle={47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages={10:1--10:15},
  editor={Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  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/68525">
    <dcterms:title>On Upward-Planar L-Drawings of Graphs</dcterms:title>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/68525/1/Angelini_2-m3r3hitv0ery2.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-11-30T09:49:50Z</dc:date>
    <dc:contributor>Angelini, Patrizio</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/68525/1/Angelini_2-m3r3hitv0ery2.pdf"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-11-30T09:49:50Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Da Lozzo, Giordano</dc:contributor>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Chaplick, Steven</dc:creator>
    <dc:creator>Da Lozzo, Giordano</dc:creator>
    <dc:creator>Angelini, Patrizio</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/68525"/>
    <dcterms:abstract>In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of e and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but the DAG is biconnected and series-parallel.</dcterms:abstract>
    <dc:language>eng</dc:language>
    <dc:contributor>Chaplick, Steven</dc:contributor>
    <dcterms:issued>2022</dcterms:issued>
  </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
Diese Publikation teilen