In mathematics and geographic information science, a shortest-path graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

defined from a set of points in the Euclidean plane. The shortest-path graph is proposed with the idea of inferring edges between a point set such that the shortest path taken over the inferred edges will roughly align with the shortest path taken over the imprecise region represented by the point set. The edge set of the shortest-path graph varies based on a single parameter ''t'' ≥ 1. When the weight of an edge is defined as its Euclidean length raised to the power of the parameter ''t'' ≥ 1, the edge is present in the shortest-path graph if and only if it is the least weight path between its endpoints.

Properties of shortest-path graph

When the configuration parameter ''t'' goes to infinity, shortest-path graph become the

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

of the point set. The graph is a subgraph of the point set's Gabriel graph and therefore also a subgraph of its

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...

References

{{reflist Geometric graphs