Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

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

+1
−0

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.

An embedding of the bipartite graph K33 into the torus.

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

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

1 answer

+0
−0

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.

History
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »