Drawing Shortest Paths in Geodetic Graphs

Kurzanzeige
dc.contributor.authorCornelsen, Sabine
dc.contributor.authorPfister, Maximilian
dc.contributor.authorFörster, Henry
dc.contributor.authorGronemann, Martin
dc.contributor.authorHoffmann, Michael
dc.contributor.authorKobourov, Stephen
dc.contributor.authorSchneck, Thomas
dc.date.accessioned2022-06-21T11:44:55Z
dc.date.available2022-06-21T11:44:55Z
dc.date.issued2021eng
dc.description.abstractMotivated 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.eng
dc.description.versionpublishedeng
dc.identifier.doi10.1007/978-3-030-68766-3_26eng
dc.identifier.urihttps://kops.uni-konstanz.de/handle/123456789/57812
dc.language.isoengeng
dc.rightsterms-of-use
dc.rights.urihttps://rightsstatements.org/page/InC/1.0/
dc.subjectEdge crossings, Unique shortest paths, Geodetic graphseng
dc.subject.ddc004eng
dc.titleDrawing Shortest Paths in Geodetic Graphseng
dc.typeINPROCEEDINGSeng
dspace.entity.typePublication
kops.citation.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}
}
kops.citation.iso690CORNELSEN, 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_26deu
kops.citation.iso690CORNELSEN, 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, Sep 16, 2020 - Sep 18, 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_26eng
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/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>
kops.conferencefieldGraph Drawing and Network Visualization, 28th International Symposium, GD 2020, 16. Sept. 2020 - 18. Sept. 2020, Vancouver, BC, Canadadeu
kops.date.conferenceEnd2020-09-18eng
kops.date.conferenceStart2020-09-16eng
kops.flag.knbibliographytrue
kops.location.conferenceVancouver, BC, Canadaeng
kops.sourcefieldAUBER, David, ed., Pavel VALTR, ed.. <i>Graph Drawing and Network Visualization, 28th International Symposium, GD 2020 : Revised Selected Papers</i>. 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_26deu
kops.sourcefield.plainAUBER, 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_26deu
kops.sourcefield.plainAUBER, 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_26eng
kops.title.conferenceGraph Drawing and Network Visualization, 28th International Symposium, GD 2020eng
relation.isAuthorOfPublicationab8dd64c-60a5-4662-9603-d40fd0e6c6f3
relation.isAuthorOfPublication.latestForDiscoveryab8dd64c-60a5-4662-9603-d40fd0e6c6f3
source.bibliographicInfo.fromPage333eng
source.bibliographicInfo.seriesNumber12590eng
source.bibliographicInfo.toPage340eng
source.contributor.editorAuber, David
source.contributor.editorValtr, Pavel
source.identifier.eissn1611-3349eng
source.identifier.isbn978-3-030-68765-6eng
source.identifier.issn0302-9743eng
source.publisherSpringereng
source.publisher.locationChameng
source.relation.ispartofseriesLecture Notes in Computer Scienceeng
source.titleGraph Drawing and Network Visualization, 28th International Symposium, GD 2020 : Revised Selected Paperseng

Dateien

Sammlungen

Informatik und Informationswissenschaft: Publikationen