# Combinatorial geodesics

[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 edges e, e' have the same direction iff

1. the path ee' is the unique shortest path between its endpoints

2. neither e nor e' is part of another unique shortest 2-edge-path through 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 called combinatorial 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 this relation of “having the same direction” and this concept of “combinatorial geodesics” been explored, under which name, and in which context?

• Geodesics in metric graphs (usually Cayley graphs with the word metric) are often considered in geometric group theory. The usual definition is quite straightforward: a geodesic is an isometrically embedded interval. See, for instance, the book Metric spaces of non-positive curvature by Bridson and Haefliger for details. – HJRW Dec 9 '12 at 13:25
• You give the square as an example to motivate your definition-by-analogy with geodesics in differential geometry. But to me, this is an example of how your analogy breaks down. If you use instead the definition HW recommends, the analogy is restored: any locally injective path in a graph is locally geodesic. – Lee Mosher Dec 9 '12 at 15:06
• @Lee: To make it clear: the square is supposed to be a counter-example and not to motivate my definition-by-analogy. – Hans-Peter Stricker Dec 9 '12 at 18:54
• Triangular and rectangular grids have no geodesics by your definition. Every edge has more than one extension as a shortest 2-edge path. – Sergei Ivanov Dec 9 '12 at 20:26
• @Sergei: There has been a flaw in my definition. I fixed it. – Hans-Peter Stricker Dec 9 '12 at 21:56

Could you say more about your examples? The reason I ask is the following observation. Suppose edges $e$ and $e'$, are in the same direction; say $e$ joins vertices $P$ and $Q$ and $e'$ joins $Q$ to $R$. Suppose, toward a contradiction, that there is another edge at $Q$, say $e''$ joining $Q$ to $X$. Since $e,e'$ have the same direction, $ee''$ cannot be a shortest path from $P$ to $X$; since its length is only 2, there must be an edge $f$ directly from $P$ to $X$. Similarly, there must be an edge $f'$ joining $R$ to $X$. But then $ff'$ is another path of length 2 from $P$ to $Q$, contrary to the assumption that $e$ and $e'$ have the same direction.
So, with $e$ and $e'$ as above, having the same direction, there cannot be any other edges at the point $Q$ where $e$ and $e'$ are incident. I could infer various further conclusions from this one, but I believe the correct (non-mathematical) inference is that either I misunderstood your definition or you didn't really mean it.