论文标题
在大地图中绘制最短路径
Drawing Shortest Paths in Geodetic Graphs
论文作者
论文摘要
受到一个事实的激励：在一个最短路径是独特的空间中，没有两次最短的路径两次相遇，我们研究了格雷格·伯德温（Greg Bodwin）提出的一个问题：鉴于一个地球图$ g $，即，任何一对顶点之间的最短路径是独特的，有一个唯一的最短路径，是否有$ g $ $ g $ g $ g $ g $ g $ g $ g $。我们通过展示了需要一对最短路径至少四次跨越四次的大地图的存在，以否定的方式回答了这个问题。对于我们构建的图形类别，交叉数的界限很紧。此外，我们展示了直径两的大地图图，这些图未接受哲学图。
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.
