[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]

I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics – all from differential geometry – can be understood in abstract graphs, i.e. what their combinatorial counterparts might be.

Specifically, I'd like to know whether the following relation among adjacent edges in a simple graph has been explored, under which name, and in which context:

Definition: Two adjacent edgese, e' have the same directioniff

the path

ee'is the unique shortest path between its endpointsneither

enore'is part of another unique shortest 2-edge-paththrough their common vertex

The first condition is motivated by the fact that geodesics in differential geometry are locally *shortest* paths and as such locally *unique*. It prevents the graph

from having edges with the same direction.

The second condition reflects the fact, that geodesics usually do not “split”. It prevents the graph

from having edges with the same direction.

Definition: Paths of length at least 2 in which adjacent edges have the same direction are calledcombinatorial geodesics.

Note, that even a single pair of edges having the same direction is a (minimal) combinatorial geodesic. *But no single edge is a combinatorial geodesic.*

It's an easy excercise to find combinatorial geodesics in some planar graphs and/or 3-vertex-connected graphs (seen as polygonizations/tilings of surfaces).

- In trees (with minimal non-leaf degree 3) there are
*no*geodesics at all. - In finite, infinite, and “torified” triangular and rectangular grid graphs there
*are*geodesics. - In infinite and in “torified” hexagonal grid graphs there are
*no*geodesics. - In polyhedral graphs there are – in general –
*no*geodesics.

Things get really interesting, I believe, when one considers e.g. *non-regular tilings of the plane* – from “slightly non-regular” (= “regular with a few perturbations”) to “completely random”. One can investigate the “geodesic structure” of such graphs: which geodesics are there, and how are they interconnected? [geodesic structure ⇄ cycle structure]

[The notion of “*true* shortest paths” between two vertices with several non-unique shortest paths between them – like in the rectangular grid – shall be subject of a follow-up question. It can be easily defined based on combinatorial geodesics.]

To repeat my questions from above:

Have

thisrelation of “having the same direction” andthisconcept of “combinatorial geodesics” been explored, under which name, and in which context?

Metric spaces of non-positive curvatureby Bridson and Haefliger for details. $\endgroup$ – HJRW Dec 9 '12 at 13:25counter-exampleandnotto motivate my definition-by-analogy. $\endgroup$ – Hans-Peter Stricker Dec 9 '12 at 18:543more comments