Back to Search
Start Over
Drawing Shortest Paths in Geodetic Graphs
- Source :
- Journal of Graph Algorithms and Applications, 26 (3), Lecture Notes in Computer Science ISBN: 9783030687656, Graph Drawing, Lecture Notes in Computer Science, 12590, Graph Drawing and Network Visualization
- Publication Year :
- 2022
- Publisher :
- Brown University, 2022.
-
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. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low.<br />Journal of Graph Algorithms and Applications, 26 (3)<br />ISSN:1526-1719
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
050101 languages & linguistics
Class (set theory)
General Computer Science
Discrete Mathematics (cs.DM)
Computer science
05 social sciences
Geodetic datum
02 engineering and technology
Space (mathematics)
Graph
Computer Science Applications
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
Shortest path problem
0202 electrical engineering, electronic engineering, information engineering
Computer Science - Computational Geometry
020201 artificial intelligence & image processing
0501 psychology and cognitive sciences
Geometry and Topology
Edge crossings
Unique shortest paths
Geodetic graphs
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-030-68765-6
- ISSN :
- 15261719
- ISBNs :
- 9783030687656
- Database :
- OpenAIRE
- Journal :
- Journal of Graph Algorithms and Applications, 26 (3), Lecture Notes in Computer Science ISBN: 9783030687656, Graph Drawing, Lecture Notes in Computer Science, 12590, Graph Drawing and Network Visualization
- Accession number :
- edsair.doi.dedup.....b09496f2c6414f25a034d4b72077c185