Drawing Shortest Paths in Geodetic Graphs
dc.contributor.author
Cornelsen, Sabine
dc.contributor.author
Pfister, Maximilian
dc.contributor.author
Förster, Henry
dc.contributor.author
Gronemann, Martin
dc.contributor.author
Hoffmann, Michael
dc.contributor.author
Kobourov, Stephen
dc.contributor.author
Schneck, Thomas
dc.contributor.editor
Auber, David
dc.contributor.editor
Valtr, Pavel
dc.date.accessioned
2021-02-19T13:31:59Z
dc.date.available
2021-01-22T19:24:04Z
dc.date.available
2021-02-19T13:31:59Z
dc.date.issued
2020
dc.identifier.isbn
978-3-030-68765-6
en_US
dc.identifier.isbn
978-3-030-68766-3
en_US
dc.identifier.issn
0302-9743
dc.identifier.issn
1611-3349
dc.identifier.other
10.1007/978-3-030-68766-3_26
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/464994
dc.description.abstract
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.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.subject
Edge crossings
en_US
dc.subject
Unique shortest paths
en_US
dc.subject
Geodetic graphs
en_US
dc.title
Drawing Shortest Paths in Geodetic Graphs
en_US
dc.type
Conference Paper
dc.date.published
2021-02-14
ethz.book.title
Graph Drawing and Network Visualization
en_US
ethz.journal.title
Lecture Notes in Computer Science
ethz.journal.volume
12590
en_US
ethz.journal.abbreviated
LNCS
ethz.pages.start
333
en_US
ethz.pages.end
340
en_US
ethz.event
28th International Symposium on Graph Drawing and Network Visualization (GD 2020) (virtual)
en_US
ethz.event.location
Vancouver, Canada
en_US
ethz.event.date
September 16-18, 2020
en_US
ethz.notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually
en_US
ethz.grant
Arrangements and Drawings (ArrDra)
en_US
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03457 - Welzl, Emo / Welzl, Emo
en_US
ethz.grant.agreementno
171681
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2021-01-22T19:24:29Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-02-19T13:32:10Z
ethz.rosetta.lastUpdated
2022-03-29T05:19:12Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Drawing%20Shortest%20Paths%20in%20Geodetic%20Graphs&rft.jtitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2020&rft.volume=12590&rft.spage=333&rft.epage=340&rft.issn=0302-9743&1611-3349&rft.au=Cornelsen,%20Sabine&Pfister,%20Maximilian&F%C3%B6rster,%20Henry&Gronemann,%20Martin&Hoffmann,%20Michael&rft.isbn=978-3-030-68765-6&978-3-030-68766-3&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-68766-3_26&rft.btitle=Graph%20Drawing%20and%20Network%20Visualization
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Conference Paper [33530]