Tuesday, February 21, 2012

Graph-encoded hypermaps

The the face coloring of the James representation of a hypermap induces an edge 3-coloring of its skeletal graph (we simply color an edge the color that is not on either of its adjacent faces.) Once colored in this way, the skeletal graph encodes the James representation of the hypermap (and thus the hypermap itself) because the face cycles can be discovered in the abstract, colored graph as the cycles of alternating edge color.

For example, below is the Walsh representation of the skeletal graph of icosahedron (interpreted as a hypermap, with white vertices subdividing its icosahedron edges.) Every Walsh representation is a bipartite map (every cycle in the map is of even length.) In consequence also, every face of a Walsh representation has an even number of sides.

The Chess representation (illustrated below,) the dual of the Walsh representation, is therefore Eulerian (all its vertices have even valence) and chess-colorable (face 2-colorable.)

The James representation (shown below) is the truncation of the Chess representation. Truncation always results in a map with exclusively 3-valent vertices (i.e., a 3-regular map.) Truncation doubles the number of sides in the old faces (here the old faces are black and white) and thus guarantees an even number of sides in those faces. The pink faces are new, but they too are guaranteed to have an even number of sides because the base map is Eulerian and has even-valent vertices. Since all of its faces have an even number of sides (but not necessarily all of its cycles), we say that the James representation of a hypermap is locally bipartite. In summary, the James representation of any hypermap is 3-regular and locally bipartite.

The graph encoding replaces the face-coloring of the James with the induced coloring of its graph:

Some more examples of graph-encoded hypermaps:

No comments: