ncatlab.org

topological map (changes) in nLab

Showing changes from revision #21 to #22: Added | Removed | Changed

Contents

Definition

A topological map (or embedded graph) MM is a graph G=(V,E,d)G = (V,E,d) (loops and multiple edges allowed) equipped with an embedding θ\theta of GG into a surface XX in such a way that:

  1. vertices x∈Vx \in V are represented as distinct points θ(x)∈X\theta(x) \in X;

  2. edges e∈Ee \in E are represented as curves θ(e)\theta(e) on the surface XX that intersect only at the vertices;

  3. the complement X∖θ(G)X \setminus \theta(G) of the graph on the surface is a disjoint union of connected components, called faces, each homeomorphic to an open disk (in other words, each face is simply connected).

These conditions can be summarized by saying that θ\theta is a cellular embedding (or “2-cell embedding”). Additionally, one may place several conditions on the underlying surface, e.g.:

A morphism of topological maps (G,X,θ)→(G′,X′,θ′)(G,X,\theta) \to (G',X',\theta') is a continuous function between the underlying spaces f:X→X′f : X \to X' whose restriction to θ(G)\theta(G) defines a homomorphism of graphs f:G→G′f : G \to G'. Sometimes one may place additional conditions on the underlying surfaces and limit the morphisms between them accordingly. For instance, typically one might assume that XX is compact, connected, oriented and without boundary, and consider a map on XX as defined up to orientation-preserving homeomorphism.

Topological maps are always considered up to the appropriate notion of homeomorphism, and they inherit various properties of the their underlying surface. surfaces: For for example, instance, a graph embedded in a connected surface is itself necessarily a connected graph, graph. and One one also speaks of thegenus of a map as the(G,X,θ)(G,X,\theta) as the genus of the underlying surface XX.

Embedded graphs versus abstract graphs

It is important to distinguish topological maps, which are graphs equipped with an embedding, from graphs which may happen to have the property of being embeddable in different surfaces. For example, a planar map is a graph equipped with a cellular embedding into the sphere, while a planar graph is a graph which is graph isomorphic to the underlying graph of a planar map. Two planar graphs are considered equivalent if they are isomorphic as graphs G 1≅G 2G_1 \cong G_2, but two planar maps are only considered equivalent if this isomorphism of graphs can be realized on their embeddings θ 1(G 1)≅θ 2(G 2)\theta_1(G_1) \cong \theta_2(G_2) by a homeomorphism of the sphere. In particular, one planar graph might have multiple, inequivalent embeddings into the sphere.

To emphasize the distinction between embedded graphs and graphs which may happen to be embeddable, one sometimes refers to the latter as abstract graphs.1

Permutation representations

One of the remarkable properties of topological maps is that they can be given a purely algebraic representation as a collection of permutations satisfying a few properties. For now, see the articles (cartographic group) and (combinatorial map).

References

A formal treatment of topological maps (including the relationship to algebraic maps and the definition of several associated categories) is in

Fairly elementary sources for background material include:

  • Arthur T. White: 1984 Graphs, groups and surfaces

This gives the Edmonds algorithm which given a graph and some permutations outputs an embedding. The original source for that is:

  • J. Edmonds (1960), A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7, 646.

More recent treatments can be found in:

  • Sergei K. Lando and Alexander K. Zvonkin, Graphs on Surfaces and Their Applications, Springer, 2004.

  • Roman Nedela, Maps, Hypermaps and Related Topics, 2007. (pdf)

Wikipedia:

Last revised on September 18, 2015 at 15:26:24. See the history of this page for a list of all contributions to it.