nLab topological map

Redirected from "embedded graph".
Contents

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 xVx \in V are represented as distinct points θ(x)X\theta(x) \in X;

  2. edges eEe \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”).

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:XXf : X \to X' whose restriction to θ(G)\theta(G) defines a homomorphism of graphs f:GGf : 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 inherit various properties of their underlying surfaces: for instance, a graph embedded in a connected surface is itself necessarily a connected graph. One also speaks of the genus of a map (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 1G 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:


  1. For more on the distinction between embedded graphs and abstract graphs, see Bruce Bartlett‘s n-Category Café post on Feynman’s Fabulous Formula.

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