I'm writing a paper in which I want to cite a (basic?) result in the topology of graphs. My question is:

Does anyone know where this theorem appears in the literature?

Or else can you simplify my proof?

Otherwise I am stuck with my quite long-winded proof. (See below.)

The theorem in question:

Let $G = (V, E)$ be a planar graph, and let $\varphi_0 : G \rightarrow \mathbb{R}^2$, $\varphi_1 : G \rightarrow \mathbb{R}^2$ be two planar, piecewise-linear embeddings. The two embeddings induce the same cyclic ordering of edges incident at each vertex of $G$ if and only if there is a homotopy $h: G \times [0, 1] \rightarrow \mathbb{R}^2$ from $\varphi_0$ to $\varphi_1$ such that for all times $t \in [0, 1]$ the function $h_t : G \rightarrow \mathbb{R}^2$ is also a planar, piecewise-linear (PPL) embedding.

Is this by any chance just a corollary of some major result?

Taking a naive approach, it seems to me that most of the work actually lies in just defining the cyclic ordering of edges incident at the vertices of $G$.

Below I sketch the naive approach I've taken, and I conclude with several questions.

Def 1: Given a graph $G = (V, E)$, if $v \in V$ is any vertex then we denote by $I(v) \subseteq E$ the set of edges incident to $v$.

Def 2: Let a graph $G = (V, E)$ and PPL embedding $\varphi : G \rightarrow \mathbb{R}^2$ be given. Then by an ordering radius we mean a real number $\rho > 0$ such that for all $v \in V$ and $e \in I(v)$ the embedding $\varphi(e)$ of the edge $e$ intersects the boundary of the $\rho$-neighbourhood $B_\rho(\varphi(v))$ of $\varphi(v)$ in exactly one point.

Obviously an ordering radius $\rho$ is so called because it allows us to define a cyclic ordering of edges in $G$ as induced by the given planar embedding $\varphi$. Centred on each vertex $v$ we draw the circle of radius $\rho$. The embedding of each edge $e \in I(v)$ crosses the circle at exactly one point $c_e$. The line from $\varphi(v)$ to $c_e$ makes some angle. Assign this angle to the edge, and order the edges by these angles.

Lemma 1: Given $G = (V, E)$ and PPL embedding $\varphi$, an ordering radius exists.

Pf sketch: Since $V$ is finite, and since for each $e \in E$ the embedding $\varphi(e)$ is made up of finitely many line segments, it is easy to choose a radius $\rho$ so small that it is an ordering radius.

Def 3: Given $G = (V, E)$ and PPL embedding $\varphi$, we define the maximal ordering radius $\rho_0(G, \varphi)$ to be the supremum of the set of all ordering radii for $G$ and $\varphi$. By Lemma 1, we know the set in question is nonempty. And it is clearly bounded since the embedding $\varphi$ is bounded. Therefore the supremum exists, and the maximal ordering radius is well-defined.

Lemma 2: If $G = (V, E)$ is a planar graph, $\varphi : G \rightarrow \mathbb{R}^2$ is a PPL embedding, and $\rho_0$ is their maximal ordering radius, then for all ordering radii $\rho \leq \rho_0$ on $G, \varphi$, the cyclic ordering induced by $\rho$ is the same as that induced by $\rho_0$.

Pf: Suppose to the contrary that there is some ordering radius $\rho_1$ and vertex $v$ whose cyclic ordering under $\rho_1$ is different to that under $\rho_0$. Then there must be some pair of edges $e, e' \in I(v)$ whose order inverts. Let $\theta : [0, 1] \rightarrow \mathbb{R}$ give the angle of edge $e$ as we continuously deform the circle of radius $\rho_0$ around $\varphi(v)$ to that of radius $\rho_1$, and likewise define $\theta'$ for edge $e'$. By the intermediate value theorem, the graphs of the functions $\theta, \theta'$ must intersect. This corresponds to a point where the embeddings $\varphi(e)$ and $\varphi(e')$ intersect, and so contradicts planarity of the embedding $\varphi$. QED

Def 4: Now, based on Lemma 2 it makes sense to define the cyclic ordering of $G$ under $\varphi$ to be that induced by the maximal ordering radius for $G$, $\varphi$.

Finally, we can prove the theorem.

Pf sketch: The key idea is the same as in the proof of Lemma 2. If the cyclic orderings induced by $\varphi_0$ and $\varphi_1$ differed for some vertex $v$, then over the homotopy $h$ we would find some time $t$ at which $h_t$ was not planar. We would do this by applying the IVT to the functions giving the angles of the edges in $I(v)$ as we deform, exactly as in the proof of Lemma 2.

Questions:

1. Is there a simpler way to define the cyclic ordering, and prove the result?

2. Is the piecewise-linear assumption even necessary? I just needed it for Lemma 1.

3. Is this result a corollary of some major theorem? Or maybe even a named theorem of its own?

4. Can anyone tell me where this result appears as a theorem in some textbook?