Publikation:

Drawing Shortest Paths in Geodetic Graphs

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2021

Autor:innen

Pfister, Maximilian
Förster, Henry
Gronemann, Martin
Hoffmann, Michael
Kobourov, Stephen
Schneck, Thomas

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-030-68766-3_26
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

AUBER, David, ed., Pavel VALTR, ed.. Graph Drawing and Network Visualization, 28th International Symposium, GD 2020 : Revised Selected Papers. Cham: Springer, 2021, pp. 333-340. Lecture Notes in Computer Science. 12590. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-68765-6. Available under: doi: 10.1007/978-3-030-68766-3_26

Zusammenfassung

Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Edge crossings, Unique shortest paths, Geodetic graphs

Konferenz

Graph Drawing and Network Visualization, 28th International Symposium, GD 2020, 16. Sept. 2020 - 18. Sept. 2020, Vancouver, BC, Canada
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CORNELSEN, Sabine, Maximilian PFISTER, Henry FÖRSTER, Martin GRONEMANN, Michael HOFFMANN, Stephen KOBOUROV, Thomas SCHNECK, 2021. Drawing Shortest Paths in Geodetic Graphs. Graph Drawing and Network Visualization, 28th International Symposium, GD 2020. Vancouver, BC, Canada, 16. Sept. 2020 - 18. Sept. 2020. In: AUBER, David, ed., Pavel VALTR, ed.. Graph Drawing and Network Visualization, 28th International Symposium, GD 2020 : Revised Selected Papers. Cham: Springer, 2021, pp. 333-340. Lecture Notes in Computer Science. 12590. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-68765-6. Available under: doi: 10.1007/978-3-030-68766-3_26
BibTex
@inproceedings{Cornelsen2021Drawi-57812,
  year={2021},
  doi={10.1007/978-3-030-68766-3_26},
  title={Drawing Shortest Paths in Geodetic Graphs},
  number={12590},
  isbn={978-3-030-68765-6},
  issn={0302-9743},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Graph Drawing and Network Visualization, 28th International Symposium, GD 2020 : Revised Selected Papers},
  pages={333--340},
  editor={Auber, David and Valtr, Pavel},
  author={Cornelsen, Sabine and Pfister, Maximilian and Förster, Henry and Gronemann, Martin and Hoffmann, Michael and Kobourov, Stephen and Schneck, Thomas}
}
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/57812">
    <dc:contributor>Kobourov, Stephen</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-06-21T11:44:55Z</dcterms:available>
    <dc:creator>Schneck, Thomas</dc:creator>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:contributor>Gronemann, Martin</dc:contributor>
    <dc:creator>Förster, Henry</dc:creator>
    <dc:creator>Kobourov, Stephen</dc:creator>
    <dcterms:title>Drawing Shortest Paths in Geodetic Graphs</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Gronemann, Martin</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-06-21T11:44:55Z</dc:date>
    <dc:creator>Hoffmann, Michael</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:contributor>Pfister, Maximilian</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Pfister, Maximilian</dc:creator>
    <dc:language>eng</dc:language>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Schneck, Thomas</dc:contributor>
    <dcterms:issued>2021</dcterms:issued>
    <dcterms:abstract xml:lang="eng">Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing.</dcterms:abstract>
    <dc:contributor>Förster, Henry</dc:contributor>
    <dc:contributor>Hoffmann, Michael</dc:contributor>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/57812"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Cornelsen, Sabine</dc:creator>
  </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