Graph Genus

Introduction

tldr, I am attempting to create an algorithm to detrmine the genus (and/or dimension) of the space in which a graph is embedded.

Imagine a 3d mesh of a torus.

Image of a torus mesh

Definitions

Vertex

We will refer to a point on a graph as a vertex, not a node or point.

Edge

We will refer to the connection between two vertices as an edge, not an arc or connection.

Walk

A sequence of edges (and their endpoints) where each edge is adjacent to the next edge.

Trail

A walk where each edge is distinct.

Path

A trail where each vertex (except maybe the first and last vertex) is distinct.

Cycle

A path that starts and ends on the same vertex.

Geodesic (Graph Theory)

A shortest path from one vertex to another.

Geodesic (Differential Geometry)

A curve representing the shortest path between two points in a surface.

Tangent Space (Differential Geometry)

A real vector space that contains the possible directions in which one can pass through a point on a manifold.

Plan

The general plan is to generate an equivalence relation of cycles of the graph. We will only consider cycles that are also geodesics. Technically a cycle cannot be a geodesic but we will define a geodesic cycle as a cycle where the geodesic between any two points on the cycle is a subpath of the cycle. We want to be able to distinguish geodesic cycles that go around different holes on the surface of the space. In the torus example, we want two equivalence classes. One that contains cycles that go around the ring (e.g. the yellow cycle) and one that contains cycles that go along the ring (e.g. the green cycle). The number of classes likely corresponds to the genus of the space.

Image of a torus mesh

Graph Tangent Spaces

The first problem is finding the geodesic cycles. There are algroithms to get the shortest paths from every vertex to every other vertex, i.e. the geodesics. Then we would need to connect them into geodesic cycles. To do this, let us define the tangent space of a vertex as the set of geodesics passing through it.

In differential geometry the tangent space of a point is the set of directions a curve can take as it passes through that point on a differentiable manifold. It is defined by the set of curves passing through the point. WHile it is not a perfect analogy, I find this similar enough to the set of shortest paths through a vertex of a graph to give the set the same name.

Using these tangent spaces, geodesics can be extended. Given a geodesic, you can take a vertex on the geodesic, say an endpoint, and find another geodesic that shares vertices (other than itself) with the original geodesic. This can be repeated until we create a cycle. Care will have to be taken to ensure that the geodesic does not take on a curve, i.e. that there are no two vertices whose shortest path is not a subset of the extended geodesic.

Some of these geodesic cycles will not be what we want. In the torus example, for any point there will be two special geodesic cycles: one going around the ring and one going along the ring. All other geodesics when extended will spiral around the ring, possibly multiple times, until making a cycle. Of course after it loops around the ring once, the shortest path between the endpoint will no longer be the extended geodesic so in this case we will only get the two special ones but this may not always be the case for other spaces.

The current algorithm is something like this:

Side Problems

Torus Triangulation

I wanted to generate example graphs for testing and illustration. The main example surface is a torus. The canonical graph on a torus is a grid along longitude and lattitude lines. This seems too simple for rigorous testing. I decided that I would like random points on the torus. I would like the edges to be constructed using a technique similar to Delaunay triangulation. I therefore decided to attempt to modify the algorithm to work on a torus.

A main detail od Delaunay triangulation is the property that if two triangles share an edge, the circumcsribed circle of one cannot contain the other triangle. If this test can be performed on the torus then the algorithm should be able to be perform as usual. Luckily we can still easily define a circle. Three point define a plane so we can find the circumscribed circle in the plane defined by the triangle. Then we can define a sphere with the same center and radius of the circle and use that to test the other triangle.