According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine connection, a geodesic is defined to be a curve whose tangent vectors remain parallel if they are transported along it. If this connection is the Levi-Civita connection induced by a Riemannian metric, then the geodesics are (locally) the shortest path between points in the space "
My questions are:
1. whether graphs in general resp. which kind of graphs fullfill the cited conditions that imply that the geodesics are (locally) shortest paths?
2. are there alternative definitions of geodesics in graphs, that are based on the generalization of straight lines, resp. on a measure for the deviation from a straight line (e.g. the angle between successive edges in case of geometric graphs)?
Background of the question:
My interest in that question comes from an attempt to generalize planar convex hulls to graphs and that in turn from the observation, that an optimal round trip through all elements of a finite subset of the points of an Euclidean plane encounters the points in the same (or reverse) order, in which they are encountered around the convex hull.
Relation of geodesics to planar convex hulls
I finally realized that the gift-wrapping algorithm http://en.wikipedia.org/wiki/Gift_wrapping_algorithm for constructing planar convex hulls could be w.l.o.g. interpreted as starting at a point with minimal $y$-coordinate, heading in positive $x$-direction and that proceeding by chosing as the next point the one that required the least change of direction, the measure of change in that case is the angle between current and subsequent direction.
The method of going as straight ahead as possible yields the convex hull as the limit cycle independent of the starting point.
Unfortunately the limit cycle need not be unique and can also have self-intersection in the case of general graphs, for which an angle between edges is defined
(however, the collection of limit cycles along with their topologies might be interesting on their own).