The Price of Upwardness

Kurzanzeige
dc.contributor.authorAngelini, Patrizio
dc.contributor.authorBiedl, Therese
dc.contributor.authorChimani, Markus
dc.contributor.authorCornelsen, Sabine
dc.contributor.authorDa Lozzo, Giordano
dc.contributor.authorHong, Seok-Hee
dc.contributor.authorLiotta, Giuseppe
dc.contributor.authorPatrignani, Maurizio
dc.contributor.authorPupyrev, Sergey
dc.contributor.authorRutter, Ignaz
dc.contributor.authorWolff, Alexander
dc.date.accessioned2026-02-02T12:48:54Z
dc.date.available2026-02-02T12:48:54Z
dc.date.issued2025-08-19
dc.description.abstractNot every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k≥1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-k-planarity is NP-complete already for k=1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face. This is the full version of a paper that appeared in the Proc. 32nd Int. Symp. Graph Drawing & Network Visualization (GD 2024)
dc.description.versionpublisheddeu
dc.identifier.doi10.46298/dmtcs.15222
dc.identifier.ppn1961820706
dc.identifier.urihttps://kops.uni-konstanz.de/handle/123456789/76072
dc.language.isoeng
dc.rightsterms-of-use
dc.rights.urihttps://rightsstatements.org/page/InC/1.0/
dc.subjectUpward drawings
dc.subjectbeyond planarity
dc.subjectupward k-planarity
dc.subjectupward outer-1-planarity
dc.subject.ddc004
dc.titleThe Price of Upwardnesseng
dc.typeJOURNAL_ARTICLE
dspace.entity.typePublication
kops.citation.bibtex
@article{Angelini2025-08-19Price-76072,
  title={The Price of Upwardness},
  year={2025},
  doi={10.46298/dmtcs.15222},
  number={3},
  volume={27},
  issn={1462-7264},
  journal={Discrete Mathematics & Theoretical Computer Science},
  author={Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  note={Article Number: 15222}
}
kops.citation.iso690ANGELINI, Patrizio, Therese BIEDL, Markus CHIMANI, Sabine CORNELSEN, Giordano DA LOZZO, Seok-Hee HONG, Giuseppe LIOTTA, Maurizio PATRIGNANI, Sergey PUPYREV, Ignaz RUTTER, Alexander WOLFF, 2025. The Price of Upwardness. In: Discrete Mathematics & Theoretical Computer Science. EPIsciences. 2025, 27(3), 15222. ISSN 1462-7264. eISSN 1365-8050. Verfügbar unter: doi: 10.46298/dmtcs.15222deu
kops.citation.iso690ANGELINI, Patrizio, Therese BIEDL, Markus CHIMANI, Sabine CORNELSEN, Giordano DA LOZZO, Seok-Hee HONG, Giuseppe LIOTTA, Maurizio PATRIGNANI, Sergey PUPYREV, Ignaz RUTTER, Alexander WOLFF, 2025. The Price of Upwardness. In: Discrete Mathematics & Theoretical Computer Science. EPIsciences. 2025, 27(3), 15222. ISSN 1462-7264. eISSN 1365-8050. Available under: doi: 10.46298/dmtcs.15222eng
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/76072">
    <dc:creator>Liotta, Giuseppe</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/76072/1/Angelini_2-1c4qi7aisoy3n5.pdf"/>
    <dc:contributor>Rutter, Ignaz</dc:contributor>
    <dcterms:title>The Price of Upwardness</dcterms:title>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:contributor>Chimani, Markus</dc:contributor>
    <dc:contributor>Da Lozzo, Giordano</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/76072"/>
    <dc:creator>Hong, Seok-Hee</dc:creator>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:creator>Wolff, Alexander</dc:creator>
    <dc:contributor>Hong, Seok-Hee</dc:contributor>
    <dcterms:abstract>Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k≥1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-k-planarity is NP-complete already for k=1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face. 

This is the full version of a paper that appeared in the Proc. 32nd Int. Symp. Graph Drawing &amp; Network Visualization (GD 2024)</dcterms:abstract>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/76072/1/Angelini_2-1c4qi7aisoy3n5.pdf"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Da Lozzo, Giordano</dc:creator>
    <dcterms:issued>2025-08-19</dcterms:issued>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:contributor>Pupyrev, Sergey</dc:contributor>
    <dc:creator>Patrignani, Maurizio</dc:creator>
    <dc:creator>Chimani, Markus</dc:creator>
    <dc:contributor>Biedl, Therese</dc:contributor>
    <dc:creator>Angelini, Patrizio</dc:creator>
    <dc:contributor>Liotta, Giuseppe</dc:contributor>
    <dc:creator>Rutter, Ignaz</dc:creator>
    <dc:language>eng</dc:language>
    <dc:contributor>Angelini, Patrizio</dc:contributor>
    <dc:creator>Pupyrev, Sergey</dc:creator>
    <dc:contributor>Wolff, Alexander</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2026-02-02T12:48:54Z</dc:date>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2026-02-02T12:48:54Z</dcterms:available>
    <dc:creator>Biedl, Therese</dc:creator>
    <dc:contributor>Patrignani, Maurizio</dc:contributor>
  </rdf:Description>
</rdf:RDF>
kops.description.funding{"first":"dfg","second":"541433306"}
kops.description.openAccessopenaccessgold
kops.flag.isPeerReviewedtrue
kops.flag.knbibliographytrue
kops.identifier.nbnurn:nbn:de:bsz:352-2-1c4qi7aisoy3n5
kops.sourcefieldDiscrete Mathematics & Theoretical Computer Science. EPIsciences. 2025, <b>27</b>(3), 15222. ISSN 1462-7264. eISSN 1365-8050. Verfügbar unter: doi: 10.46298/dmtcs.15222deu
kops.sourcefield.plainDiscrete Mathematics & Theoretical Computer Science. EPIsciences. 2025, 27(3), 15222. ISSN 1462-7264. eISSN 1365-8050. Verfügbar unter: doi: 10.46298/dmtcs.15222deu
kops.sourcefield.plainDiscrete Mathematics & Theoretical Computer Science. EPIsciences. 2025, 27(3), 15222. ISSN 1462-7264. eISSN 1365-8050. Available under: doi: 10.46298/dmtcs.15222eng
relation.isAuthorOfPublicationab8dd64c-60a5-4662-9603-d40fd0e6c6f3
relation.isAuthorOfPublication.latestForDiscoveryab8dd64c-60a5-4662-9603-d40fd0e6c6f3
source.bibliographicInfo.articleNumber15222
source.bibliographicInfo.issue3
source.bibliographicInfo.volume27
source.identifier.eissn1365-8050
source.identifier.issn1462-7264
source.periodicalTitleDiscrete Mathematics & Theoretical Computer Science
source.publisherEPIsciences
temp.internal.duplicatesitems/10dff9d2-fe14-456b-89f0-633f51044dbc;true;The Price of Upwardness

Dateien

Originalbündel

Gerade angezeigt 1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
Angelini_2-1c4qi7aisoy3n5.pdf
Größe:
745.92 KB
Format:
Adobe Portable Document Format
Angelini_2-1c4qi7aisoy3n5.pdf
Angelini_2-1c4qi7aisoy3n5.pdfGröße: 745.92 KBDownloads: 13

Sammlungen

Informatik und Informationswissenschaft: Publikationen