Post History

60%

+1 −0

Q&A How do I unambiguously define the facial circuits in a $2$-cell embedding of a graph into a surface?

1 answer · posted 1y ago by The Amplitwist‭ · last activity 11mo ago by The Amplitwist‭

Question topology graph-theory

#2: Post edited by $user avatar$ The Amplitwist‭ · 2024-04-21T04:16:13Z (about 1 year ago)
added thoughts

Copy Link

Raw

Markdown

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.
<img src="https://math.codidact.com/uploads/so2nfz9v27646b564ytvedplvfyn" alt="An embedding of the bipartite graph K33 into the torus." width="400px">
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 (unique?) 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)$.
Hopefully, 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 I presume it isn't too difficult, even though I am not able to complete the argument.~~
~~### References~~
**[Kag37]** Kagno, I. N. [*The mapping of graphs on surfaces.*](https://doi.org/10.1002/sapm193716146) J. Math. Phys., Massachusetts, 16, 46–75 (1937). [Zbl 0017.42701](https://zbmath.org/0017.42701), [JFM 63.0550.02](https://zbmath.org/63.0550.02)
**[EEK82]** Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S. [*Regular tessellations of surfaces and $(p,q,2)$-triangle groups.*](https://doi.org/10.2307/2007049) Ann. Math. (2) 116, 113–132 (1982). [Zbl 0497.57001](https://zbmath.org/0497.57001)

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.
<img src="https://math.codidact.com/uploads/so2nfz9v27646b564ytvedplvfyn" alt="An embedding of the bipartite graph K33 into the torus." width="400px">
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.*](https://doi.org/10.1002/sapm193716146) J. Math. Phys., Massachusetts, 16, 46–75 (1937). [Zbl 0017.42701](https://zbmath.org/0017.42701), [JFM 63.0550.02](https://zbmath.org/63.0550.02)
**[EEK82]** Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S. [*Regular tessellations of surfaces and $(p,q,2)$-triangle groups.*](https://doi.org/10.2307/2007049) Ann. Math. (2) 116, 113–132 (1982). [Zbl 0497.57001](https://zbmath.org/0497.57001)

#1: Initial revision by $user avatar$ The Amplitwist‭ · 2024-04-18T04:38:52Z (about 1 year ago)

Copy Link

Raw

Markdown

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.

<img src="https://math.codidact.com/uploads/so2nfz9v27646b564ytvedplvfyn" alt="An embedding of the bipartite graph K33 into the torus." width="400px">

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 (unique?) 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)$.
Hopefully, 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 I presume it isn't too difficult, even though I am not able to complete the argument.

### References

**[Kag37]** Kagno, I. N. [*The mapping of graphs on surfaces.*](https://doi.org/10.1002/sapm193716146) J. Math. Phys., Massachusetts, 16, 46–75 (1937). [Zbl 0017.42701](https://zbmath.org/0017.42701), [JFM 63.0550.02](https://zbmath.org/63.0550.02)

**[EEK82]** Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S. [*Regular tessellations of surfaces and $(p,q,2)$-triangle groups.*](https://doi.org/10.2307/2007049) Ann. Math. (2) 116, 113–132 (1982). [Zbl 0497.57001](https://zbmath.org/0497.57001)

topology graph-theory

Communities

Post History