Regular map (graph theory)

Overview

Regular maps are typically defined and studied in three ways: topologically, group-theoretically, and graph-theoretically.

Topological approach

Topologically, a map is a 2-cell decomposition of a closed compact 2-manifold.

The genus g, of a map M is given by Euler's relation χ ( M ) = | V | − | E | + | F | which is equal to 2 − 2 g if the map is orientable, and 2 − g if the map is non-orientable. It is a crucial fact that there is a finite (non-zero) number of regular maps for every orientable genus except the torus.

Group-theoretical approach

Group-theoretically, the permutation representation of a regular map M is a transitive permutation group C, on a set Ω of flags, generated by three fixed-point free involutions r₀, r₁, r₂ satisfying (r₀r₂)²= I. In this definition the faces are the orbits of F = <r₀, r₁>, edges are the orbits of E = <r₀, r₂>, and vertices are the orbits of V = <r₁, r₂>. More abstractly, the automorphism group of any regular map is the non-degenerate, homomorphic image of a <2,m,n>-triangle group.

Graph-theoretical approach

Graph-theoretically, a map is a cubic graph Γ with edges coloured blue, yellow, red such that: Γ is connected, every vertex is incident to one edge of each colour, and cycles of edges not coloured blue, have length 4. Note that Γ is the flag graph or graph encoded map (GEM) of the map, defined on the vertex set of flags Ω and is not the skeleton G = (V,E) of the map. In general, | Ω | = 4|E|.

A map M is regular iff Aut(M) acts regularly on the flags. Aut(M) of a regular map is transitive on the vertices, edges, and faces of M. A map M is said to be reflexible iff Aut(M) is regular and contains an automorphism ϕ that fixes both a vertex v and a face f, but reverses the order of the edges. A map which is regular but not reflexible is said to be chiral.

Examples

The following is a complete list of regular maps in surfaces of positive Euler characteristic, χ: the sphere and the projective plane..

The images below show three of the 20 regular maps in the triple torus, labelled with their Schläfli symbols.

Toroidal polyhedra

Regular maps exist as torohedral polyhedra as finite portions of Euclidean tilings, wrapped onto the surface of a duocylinder as a flat torus. These are labeled {4,4}_b,c for those related to the square tiling, {4,4}. {3,6}_b,c are related to the triangular tiling, {3,6}, and {6,3}_b,c related to the hexagonal tiling, {6,3}. b and c are whole numbers. There are 2 special cases {b,0) and (b,b) with reflective symmetry, while the general cases exist in chiral pairs (b,c) and (c,b).

Regular maps of the form {4,4}_m,0 can be represented as the finite regular skew polyhedron {4,4 | m}, seen as the square faces of a m×m duoprism in 4-dimensions.

Here's an example {4,4}_8,0 mapped from a plane as a chessboard to a cylinder section to a torus. The projection from a cylinder to a torus distorts the geometry in 3 dimensions, but can be done without distortion in 4-dimensions.

In generally regular toroidal polyhedra {p,q}_b,c can be defined if either p or q are even, although only euclidean ones above can exist as toroidal polyhedra in 4-dimensions. In {2p,q}, the paths (b,c) can be defined as stepping face-edge-face in straight lines, while the dual {p,2q} forms will see the paths (b,c) as stepping vertex-edge-vertex in straight lines.