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



Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible
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. 


