MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a finite, planar graph. In this question I consider a path in $G$ to be a finite sequence of vertices $v_1,\dots,v_n$ of $G$, where $v_i$ is adjacent to $v_{i-1}$ for $i=2,\dots,n$. A subpath of this path is a subsequence of consecutive terms from $v_1,\dots,v_n$ (possibly only a single term).

Given a path $\gamma$ in $G$, there are two elementary operations that we can apply to $\gamma$ to transform it into another path with the same start and end vertices. The first of these operations is to replace a subpath of $\gamma$ that travels part (or possibly all) of the way round a face of $G$ with a subpath that travels in the opposite direction round the face, along the remaining part of the face boundary. The second operation is to replace a subpath of $\gamma$ of the form $v_1,v_2,v_1$ with $v_1$ (or vice versa).

It seems that using a sequence of elementary operations such as these, we can transform a given path between two vertices $a$ and $b$ to any other path between $a$ and $b$. At least, a result of this type would be true if I specified the elementary operations more precisely than I have done.

Could somebody please direct me to literature on this topic? No doubt there are stronger results than the one I've indicated here, and better descriptions of the transformations involved. Any suggestions for suitable references would be greatly appreciated.

share|cite|improve this question
What is a "face" of $G$? – Vidit Nanda Aug 8 '13 at 19:47
Lyndon and Schupp, "Combinatorial group theory", read about van Kampen diagrams. – Mark Sapir Aug 8 '13 at 20:31
@ViditNanda: I think a "face" is a cycle here. – Samuele Giraudo Aug 8 '13 at 21:04
No, a face is a finite diameter connected component of $\mathbb{R}^2$ minus the graph. – Mark Sapir Aug 8 '13 at 21:49
Thank you Mark, that reference is useful to me. And yes, the definition of face I had in mind is the one Mark describes. – Ian Short Aug 9 '13 at 11:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.