1
$\begingroup$

I am looking for a list of necessary and sufficient conditions for two loops on a (compact connected orientable) surface to be homotopic that could be made into a purely combinatorial definition of homotopy in embeddable (but not necessarily embedded) graphs (esp. triangulations of the surface). Or is there no chance for such a definition because homotopy is an essentially continuous concept, and graphs are discrete?

  1. If two loops intersect transversally in exactly one point they are not homotopic to each other and not homotopic to a contractible loop.

  2. If two loops - each on its own - disconnect the surface they are both contractible and thus homotopic to each other.

  3. If two loops are shorter than the systole of the surface they are both contractible and thus homotopic to each other.

(The latter corresponds to a trivial sufficient condition for two cycles of a triangulation to be homotopic: if they are triangles.)

$\endgroup$
1
$\begingroup$

There is a classical combinatorial algorithm to decide if two loops on a surface are homotopic, originally described by Max Dehn in 1912. For closed walks in arbitrary surface graphs, there is an efficient implementation of Dehn's algorithm that runs in $O(n+L+L')$ time, where $n$ is the number of edges in the graph and $L$ and $L'$ are the lengths of the walks. For details, see my SODA 2013 paper with Kim Whittlesey: "Transforming Curves on Surfaces Redux".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.