How do I unambiguously define the facial circuits in a $2$-cell embedding of a graph into a surface?
Suppose that $\Gamma$ is a connected, locally finite graph that is embedded into a closed, connected surface $M$. The faces of this embedding are the connected components of $M - \Gamma$ (we choose to denote the image of the embedding also by $\Gamma$). Let us assume that the embedding is such that each face is homeomorphic to a disc (this is called a $2$-cell embedding).
I would like to describe the boundary of a face $F$ by a walk in $\Gamma$. If $F \cup \partial F$ is homeomorphic to a closed disc, then I can do this by restricting such a homeomorphism to the boundary to get a closed path that passes through the vertices and edges incident on $F$ in a specific order. But in general it is possible that $F \cup \partial F$ is not homeomorphic to a closed disc even when we have a $2$-cell embedding. Figure 4b in [Kag37], reproduced below, shows a $2$-cell embedding of $K_{3,3}$ into the torus which has such a face.
So, I want to instead say that if $\varphi \colon B(0,1) \to M$ is a homeomorphism from the unit ball in $\mathbf{R}^2$ onto the face $F$, then there is a surjective continuous function $\Phi \colon B[0,1] \to F \cup \partial F$ from the closed unit ball in $\mathbf{R}^2$ to the union of $F$ and its boundary, which extends $\varphi$ on $B(0,1)$. (Note that if $\Phi$ exists, then it is unique, since $M$ is Hausdorff.) I can then deduce the facial walk of $F$ in $\Gamma$ from the data $\Phi$.
Question: How can I go about this? My primary goal is to be able to unambiguously define the facial circuits of an embedding, though I would be happy to just know how to define $\Phi$ from $\varphi$ for now.
I found a similar assertion made in the [EEK82], where the authors say:
[L]et $D_p$ denote a $p$-gon, that is, a closed disk whose boundary is divided into $p$ edges by $p$ vertices. Given a closed face $\alpha$ of $\Gamma$ there exists a unique positive integer $p$ and a characteristic map $\phi \colon (D_p, \partial D_p) \to (\alpha, \partial \alpha)$ which is an embedding on the interior of $D_p$ and on the interior of each of the $p$ edges along $\partial D_p$.
But they do not prove the existence of such a characteristic map, so perhaps it isn't too difficult?
Some thoughts
We know that $M$ can be embedded into Euclidean space of sufficiently large dimension. So, we can view $\varphi$ as a map of metric spaces. Then, since the closed unit ball is compact, there is a continuous extension $\Phi$ if and only if $\varphi$ is uniformly continuous.
This seems a bit odd to me. Can we assume without loss of generality that the homeomorphism $\varphi$ from the open unit disc to the face $F$ is uniformly continuous?
References
[Kag37] Kagno, I. N. The mapping of graphs on surfaces. J. Math. Phys., Massachusetts, 16, 46–75 (1937). Zbl 0017.42701, JFM 63.0550.02
[EEK82] Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S. Regular tessellations of surfaces and $(p,q,2)$-triangle groups. Ann. Math. (2) 116, 113–132 (1982). Zbl 0497.57001
1 answer
This is answered in the paper Embedding graphs in surfaces (P. Hoffman and B. Richter, J. Comb. Theory, Ser. B 36, 65–84 (1984; Zbl 0514.05028)). Quoting from the introduction:
There are certain foundational results in the overlap between graph theory and the topology of surfaces whose proofs seem both to the [sic] relatively lengthy and not to appear in the literature. In particular an earlier version of this paper was motivated by a query from Jack Edmonds about the proof that any graph contained in a surface is a subcomplex of the $1$-skeleton of a suitably chosen triangulation of that surface. His basic results for the orientable case [Edm60], whose proofs appear in [You63], and many other papers in topological graph theory, depend on this fact. On the other hand, the proof of this "folk theorem" (Theorem 1.3) certainly uses nothing but topological facts known prior to 1925 plus elementary arguments.
We have included a number of other results in topological graph theory. For example, the method of proof of Theorem 1.3, namely Theorem 2.3, is used to obtain a rigorous definition of the "combinatorial boundary" of a face of an embedded graph. The same theorem is useful is [sic] discussing "equivalent" embeddings and the various combinatorial schemes for embeddings which have been developed.
References
[Edm60] J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. (1960), 646.
[You63] J. W. T. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303–315.
0 comment threads
0 comment threads