4
$\begingroup$

[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

enter image description here

from having edges with the same direction.

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

enter image description here

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – HJRW
    Commented Dec 9, 2012 at 13:25
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lee Mosher
    Commented Dec 9, 2012 at 15:06
  • $\begingroup$ @Lee: To make it clear: the square is supposed to be a counter-example and not to motivate my definition-by-analogy. $\endgroup$
    – Hans-Peter Stricker
    Commented Dec 9, 2012 at 18:54
  • $\begingroup$ @HW: Isn't every connected graph a metric graph with the usual distance function? What I am looking for is a more restricted notion of geodesic: one, that is locally unique, such that not all shortest paths are geodesics, not even all unique shortest paths. $\endgroup$
    – Hans-Peter Stricker
    Commented Dec 10, 2012 at 9:39
  • $\begingroup$ Hans - OK, that's fine. I had interpreted your question 'Have ... the concept of "combinatorial geodesic" been explored ... and in which context?' generally. But I now see that you're interested in something quite specific. I'd like to know why you want such a strange notion, when a robust definition of combinatorial geodesic already exists. $\endgroup$
    – HJRW
    Commented Dec 12, 2012 at 11:13

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Andreas: Having corrected the definition, please let me point out, that there may be several unique shortest 2-edge-paths through a single point (see the rectangular grid graph), but no two of them share an edge. On the other side, every edge can have the same direction with at most two other edges. $\endgroup$
    – Hans-Peter Stricker
    Commented Dec 10, 2012 at 8:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .