Drawing Shortest Paths in Geodetic Graphs

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

CORNELSEN, 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, pp. 333-340. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-68765-6. Available under: doi: 10.1007/978-3-030-68766-3_26

@inproceedings{Cornelsen2021Drawi-57812, title={Drawing Shortest Paths in Geodetic Graphs}, year={2021}, doi={10.1007/978-3-030-68766-3_26}, number={12590}, isbn={978-3-030-68765-6}, issn={0302-9743}, address={Cham}, publisher={Springer}, 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 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/rdf/resource/123456789/57812"> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:creator>Schneck, Thomas</dc:creator> <dc:language>eng</dc:language> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-06-21T11:44:55Z</dc:date> <dc:creator>Hoffmann, Michael</dc:creator> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:creator>Förster, Henry</dc:creator> <dc:rights>terms-of-use</dc:rights> <dc:creator>Pfister, Maximilian</dc:creator> <dc:contributor>Kobourov, Stephen</dc:contributor> <dc:creator>Kobourov, Stephen</dc:creator> <dc:contributor>Hoffmann, Michael</dc:contributor> <dc:creator>Gronemann, Martin</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <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> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Gronemann, Martin</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-06-21T11:44:55Z</dcterms:available> <dcterms:issued>2021</dcterms:issued> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Förster, Henry</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/57812"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dcterms:title>Drawing Shortest Paths in Geodetic Graphs</dcterms:title> <dc:contributor>Schneck, Thomas</dc:contributor> <dc:contributor>Pfister, Maximilian</dc:contributor> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account