Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible

Question

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).

Answer 1

An interesting class of graphs are the median graphs ( see here http://en.wikipedia.org/wiki/Median_graph). If you fill in all (maximal) subgraphs which are Hamming cubes you will get a $CAT(0)$ cubical complex. The $CAT(0)$ distance is given by putting the euclidian metric in each cube and then taking the shortest path in the whole complex. It is really a $L_2$ metric versus the initial graph metric which is $L_1$. The new $CAT(0)$ geodesics (which are unique between two points-versus the many shortest paths in the initial graph) look more like "straight lines" in the usual sense (and indeed you can embed bounded parts of the complex into euclidian spaces such that the geodesic you are interested in is straight in the usual sense). Eg. $\mathbb{Z^2}$ is turned into $\mathbb{R^2}$ this way.

The connection between median graphs and $CAT(0)$ cubical complexes is worked out by Chepoi here: http://pageperso.lif.univ-mrs.fr/~victor.chepoi/cat0.pdf

I hope it helps a bit.

Answer 2

I imagine the property you want is very rare, regardless of how you define "straightest path". Here is one example though. Consider the Cayley graph of the free group presented by $\langle x,y|\rangle$, i.e., the infinite 4-valent regular graph. Take the angle between two edges leaving a vertex to be $\pi$ if they are distinct and $0$ if they are the same edge. Then geodesics are curves which curve as little as possible, i.e., always go through straight angles.