Thursday, February 23, 2012

Visualizing map operations as vertex inflations

One way to visualize map operations is as an inflation of vertices, like blowing bubbles. For example, let’s use a triangle on the sphere as our base map.

We have drawn the triangle on the sphere, though it may look like we have drawn it on the plane. Given any topological map on the sphere, we can place all but perhaps one vertex on the front side of the sphere. We will draw spherical maps on the plane in this way, knowing that occasionally we will need to imagine what is happening at a singular point on the back side of the sphere.

OK, let’s dispense with drawing little black dots at the vertices, except where they are 2-valent and needed, and redraw the original vertices as little bubbles. This already gives us the truncate of the base map.

Inflate the vertices some more, and eventually they meet each other at the midpoint of the edges. That forms medial:

Continued inflation of the bubbles causes the frontier of meeting to enlarge from a point to a line segment, forming leapfrog:

Inflating still more causes the bubbles to meet at the center of the original faces. This is dual. (In the drawing, the dashed arrows indicate that the meeting of three of the bubbles takes place at the singular point on the rear of the sphere.)

We have shown that the dual of the triangle on the sphere is the theta graph on the sphere, a graph with 2 vertices and 3 edges.

We may choose to now consider Du(t) to be the base map. Inflating its two vertices to form its truncate, we discover that we are just running the same film in reverse. We have just discovered the identity:

Tr(Du()) = Le().

Playing the rest of the film back we also discover these map operation identities:

Me(Du()) = Me(),

Le(Du()) = Tr(),

Du(Du()) = Id(),

where Id() is the identity operation, the operation that does not change the base map.

Altogether, there are 5 map operations (Id, Tr, Me, Le, and Du) that can be understood as inflations of the original vertices. This chart summarizes the sequence. The middle column shows polar views of the action of the operation on the map of a monogon on the sphere. The right column shows the action of the map operation on the quadrilateral associated with each edge of the base map. Look first at the diagrams for Id, the identity operation, to get oriented.

The map operation subdivide, Su(), inserts a new vertex at the midpoint of each edge in the base map. So Su(t) is:

Starting from Su(t), we now have two classes of vertices, old and new, that we can inflate differently. If we choose not to inflate the new vertices, we get a rather uninteresting sequence that reprises Id-Tr-Me-Le-Du with an additional vertex in all but Me (where it is redundant.)

Inflating only the new vertices first gives a truncation of only the new vertices that we will call lens, Ln():

Inflating the new vertices further causes them to meet at the old vertices, which gives parallel:

Inflating still further gives chamfer:

Inflating still more closes up the non-inflated faces completely, giving radial:

The following chart summarizes the map operations produced by inflating the new, mid-edge vertices:

Finally, if both original vertices and mid-edge vertices are inflated (neither being allowed to contract to a point) we get these map operations:

Wednesday, February 22, 2012

Hypermap representations of ordinary maps II

This diagram summarizes the map operations needed to go directly from an ordinary map to its representations as a hypermap (having 2-valent hyperedges.)

In the diagram, for any map operation Mp, Mp'() = Mp(Du()), and Mp*() = Du(Mp()).

The map operation here named meta (following Conway) is sometimes called full bisection, barycentric subdivision, 2-D subdivision or dual triangle quadrisection.

The map operation here named bevel (following most of the map operations literature) is sometimes called omnitruncation.

The map operation here named parallel is sometimes called parallelization.

The map operation here named subdivide is sometimes called Su1 or 1-dimensional subdivision.

The composite map operation ring is given by: Ri() = Me(Su()).

Relations between hypermap representations

The six most important hypermap representations (Walsh, James, Cori, Belyi, Chess, and Quad) are tightly interrelated by map operations. This diagram summarizes their relationship.

In short, Walsh and Chess are duals; Belyi and James are duals; Cori and Quad are duals; Belyi can be derived from Walsh by kis, James can be derived from Walsh by leapfrog; Cori can be derived from Walsh by medial; Quad can be derived from Walsh by radial.

Alternately, the derivations can begin at Chess, the dual of Walsh. James can be derived from Chess by truncate, Belyi can be derived from Chess by ko; Cori can be derived from Chess by medial; Quad can be derived from Chess by radial.

The map operation here called kis (following Conway) has sometimes been called P3, Su2, 2-dimensional subdivision, stellation, or omnicapping.

The map operation here called leapfrog (following most of the map operations literature) has sometimes been called tripling or dual √3 trisection.

The map operation here called ko is associated in the computer graphics literature with Kobbelt, and has sometimes been called primal √3 trisection. Note that Ki(M) = Ko(Du(M)). That corrects an error in my paper for ISAMA 2011.

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:

Friday, February 17, 2012

Belyi Triangulations

Every orientable hypermap is a associated with a Belyi triangulation—and thereby with a conformal mapping to the Riemann sphere. (Ordinary maps become hypermaps in their Walsh representation, that is, with a white vertex subdividing every original edge of the map.)

In the illustrations below, the darkened triangles map to the lower hemisphere of the Riemann sphere. The black, white, pink vertices map respectively to the points 0, 1, ∞ on the real equatorial circle of the Riemann sphere.

If the Riemann sphere is imagined flattened and stretched into a triangle with vertices at 0, 1, and ∞, these conformal mappings onto the sphere also describe ways to origami fold the topological surface into a triangle. [Di Francesco and Guitter]

Wednesday, February 15, 2012

Representation of hypermaps as flow fields

The pentakis dodecahedron hypermap as a flow field.

The distinction we make between hypervertices and hyperedges of a hypergraph amounts to a nominal orientation of the graph: hypervertices (black vertices) are nominally the sources, hyperedges (white vertices) are nominally the sinks. The hyperfaces are the saddles in this nominal flow. Taking the transpose dual (doing a black/white color swap) merely reverses the nominal direction of the flow. The representation above (lacking arrows to indicate a direction of flow) represents both of the transpose duals of the pentakis dodecahedron hypermap. The geometrically important varieties of the hextuplet of hyperduals are the ones that change the color of the saddles. The two diagrams below each represent a different pair of transpose duals from among the hextuplet of hyperduals of the pentakis dodecahedron.

The two white-saddle hyperduals of the pentakis dodecahedron hypermap.

The two black-saddle hyperduals of the pentakis dodecahedron hypermap.

Tuesday, February 14, 2012

Hypermap representations of ordinary maps

When starting from an ordinary map M, the operation of inserting a white vertex into each original edge (to obtain the map's Walsh representation as a hypermap) can be subsumed in a composite map operation that directly gives one of the hypermap representations.

If Mp() is a map operation, denote as as Mp'(), the rotation of Mp, the composite operation Mp(Du()). Then the hypermap representations of an ordinary map M are:

W = Su(M)

X = Du(Su(M)) = Pa(Du(M)) = Pa'(M)

J = Le(Su(M)) = Be(M)

B = Du(Be(M)) = Mt(M)

C = Me(Su(M)) = Ri(M)

Q = Du(Me(Su(M)) = Ra(Su(M)) = Du(Ri(M))

where the newly referenced map operations are parallel, bevel, meta, and ring.

Here are examples for the skeletal graph of the pentakis dodecahedron (the dual of the buckyball) embedded as a hypermap in the sphere.







Friday, February 10, 2012

Hypergraphs and Colored Maps

A graph, in general terms, is a set of vertices connected by edges. Finding good colorings for the vertices (or edges) of a graph may seem like a hobby interest, but, in fact, graphs bearing certain rule-based colorings represent mathematical objects that are more general than graphs themselves. By bearing colors, graphs let us see objects that could not be quite so easily drawn.

Here we allow a graph to have both parallel edges and self-loops. Such a graph is sometimes called a pseudograph or a general graph. We distinguish a graph having neither parallel edges nor self-loops as a simple graph; a graph having parallel edges but no self-loops is distinguished as a multigraph. We will only consider graphs whose vertex sets and edge sets are finite. Graphs (but not, later, maps) are allowed to be disconnected.

The most important graph coloring is a coloring of the vertices of a graph in two colors consistent with a rule that no two vertices of the same color may share an edge. Unless otherwise stated, graph colorings are assumed to be vertex colorings, so such a vertex coloring is often simply called a proper bicoloring of the graph; or, still more simply (since there is infrequent need to discuss improper colorings that disobey the rule,) a bicoloring of the graph.

A bicoloring is not always possible. The graph on the left side of the figure above is an example. Any self-loop (the example has two of them) violates the coloring rule that the vertices at the two ends of an edge will be differently colored. A graph whose vertices can be properly two-colored is called bipartite (example in the center of the figure;) a graph that has indeed been colored in such a way is called bicolored. A graph is bipartite if and only if all of its cycles have even length. (Thus, all trees are bipartite since they have only cycles of zero length.)

As it turns out, there are only two ways to bicolor a given bipartite graph—the one option is to swap colors. Nonetheless, given a bipartite graph, we do not yet have a bicolored graph until we actually make this bivariate choice of coloring.

A graph concerns things called vertices and edges, and a relation between them called connection or incidence. We habitually draw dots for vertices and draw line segments for edges. What we seldom notice is that the line segments are doing double duty: representing both the edges and the "connection" relation. Suppose instead we draw black dots and call them "vertices," and draw white dots and call them "edges," and we use line segments purely to represent connection. In this more fastidious kind of graph drawing, the pseudograph as drawn at the left above is meaningless; what we really wanted to express there, is drawn in the proper way on the right side of the figure as a bicolored multigraph.

Recapping, when we drew a pseudograph in this fastidious new way, we ended up with a multigraph that was bicolored: a multigraph having white vertices subdividing the line segments we formerly designated as edges. We will call this new kind of graph drawing a König representation of the graph. It is simple to convert a naive graph drawing to a König representation: just subdivide every edge in the drawing with a white vertex.

Going further, we can liberate ourselves from a world where every white vertex in a König representation is 2-valent. What we need is a generalization of the concept of a graph called a hypergraph. More particularly, we need a hypergraph with multiplicity, what Babaev terms a pseudo-hypergraph. I prefer the term multiset hypergraph.

Definition: A multiset hypergraph is a generalization of the concept of a graph such that every bicolored multigraph is a König representation of a multiset hypergraph.

An edge (or hyperedge) in a multiset hypergraph is allowed to connect to any of its vertices with multiplicity n, where n is any non-negative integer. (Since the connection relation is reciprocal, we may put it the other way around: each vertex is allowed to connect to each of its edges with multiplicity n, where n is any non-negative integer.) We can phrase this in terms of the incidence matrix of the graph, that is, the matrix where rows represent vertices, columns represent edges, and the entries are the multiplicity of connection between each vertex and edge.

Alternate Definition: A multiset hypergraph is a generalization of the concept of a graph such that every matrix of non-negative integers is the incidence matrix of a multiset hypergraph.

A multiset is a generalization of the idea of a set where members are allowed to appear more than once (they may only appear once in a set.)

Sets are familiarly illustrated with Venn diagrams, where overlapping closed curves show set intersection. In a similar way, multisets can be diagrammed with amoeba diagrams, where wiggly, closed, and sometimes self-overlapping curves express the idea of multiple inclusion. Black dots in the amoeba diagram represent vertices. The closed curves represent edges. Overlaps of the curves (edges) only count when they contain a dot (vertex)—the purpose being to count multiplicity of inclusion.

An amoeba diagram of a set hypergraph, shown above with its incidence matrix on the left, has edges that singly include certain vertices. An amoeba diagram of a multiset hypergraph, shown above with its incidence matrix on the right, has edges that multiply include certain vertices. In the following, for brevity, the term "hypergraph" will mean "multiset hypergraph."

We can obtain the König representation of a hypergraph from its amoeba diagram by imagining the amoebas to "deflate," contracting their "legs" to line segments, their "torsos" to white vertices:

In the deflation process, what was formerly the incidence matrix of the hypergraph is rechristened the biadjacency matrix of the König representation.

In the figure below, the simplest hypergraphs are shown as both amoeba diagrams and König representations. They are, left to right: an isolated vertex; an empty edge; 1-, 2-, and 3-brins; two parallel 1-brins; and a classical edge.

Notice that the formerly sharp distinction between a self-loop and a brin ("sprig" in French) was a mirage: a self-loop is just a 2-brin.

A general graph is said to be properly embedded if it lies in a smooth, closed, surface in such a way that edges cross each other only at vertices; and such that all that would remain of the surface if the multigraph's edges were to be deleted, would be a disjoint union of topological disks. For example, the skeletal graph of a tetrahedron can be drawn on the torus in a variety of inequivalent ways, two of which are shown in the figure below:

The embedding on the right is a proper embedding. The embedding on the left is an improper embedding because one of its faces is not a disk.

Definition: A multiset hypergraph is said to be properly embedded in a surface if its König representation is.

It is not always possible to properly embed a given König representation in a given surface. Nonetheless, it is a theorem that every multigraph (in fact, every general graph) has a proper embedding in some surface. Most commonly, the König multigraph can be properly embedded in a spectrum of topologically different surfaces, often it can be properly embedded in multiple inequivalent ways in each.

Definition: A hypermap is a smooth, closed, connected surface taken together with a proper embedding of a König representation of a hypergraph in the surface, considered up to homeomorphism.

By "up to homeomorphism" we mean that we are only interested in these embeddings as topological objects: if two hypermaps can be brought into congruence by a smooth deformation (homeomorphism) of the underlying surfaces, they are, and were always, the same hypermap. Since only a connected graph can be properly embedded in a connected surface, there are, by definition, no disconnected hypermaps. We will also specifically exclude isolated vertices and empty edges from becoming maps, so the smallest and simplest hypermap is an embedding of a 1-brin in the sphere:

What will interest us about hypermaps is their representation as colored maps.

The Walsh representation is simply a drawing of the König representation on the surface. Note the distinction: the König representation represents an abstract hypergraph (i.e., an unembedded hypergraph,) while the Walsh representation represents a hypermap (an embedded hypergraph.) So the figure above is the Walsh representation of a 1-brin in the sphere.

Given any map, there are other maps related to it via map operations. Map operations will be our guide in seeking alternatives to the Walsh representation. Map operations are not defined to operate on colored maps, but a simple principle of color inheritance works well. For example, in the familiar (Poincaré) dual, new faces descend from old vertices, so they should inherit their colors. Map operations and their compositions are written in an abbreviated two-letter functional notation that is self-explanatory. For example, the insertion of vertices at the midpoint of edges (used earlier in constructing the König representation) is the action of the map operation subdivide:

W= Su(M)

where W is the Walsh representation of some ordinary map M. (It must be understood that the new vertices inserted by subdivide are to be colored white.)

The Chess representation is:

X = Du(W),

where the map operation (Poincaré) dual, turns W into a representation with black and white regions representing the hypervertices and hyperedges respectively. New pink vertices represent the hyperfaces. Because the Walsh is bipartite (all cycles have even length) its dual is Eulerian and chess-colorable (all vertices have even valence, and the map is face 2-colorable.) Below are the Walsh representation of a 1-brin on the sphere (left) with its dual, the Chess representation (right.)

The James representation is:

J = Le(W) = Tr(Du(W)) = Du(Ki(W)),

where the newly referenced map operations are leapfrog, truncate, and kis. This gives a 3-regular map with black, white, and pink regions representing hypervertices, hyperedges, and hyperfaces respectively. The James is expressed most simply as the truncation of the Chess representation. Below, for the 1-brin on the sphere, the Chess representation (left) and James representation (right.)

The Belyi triangulation is:

B = Du(Le(W)) = Ki(W),

which gives a triangle-faced map with a proper vertex 3-coloring. The Belyi is dual to the James. Below, the James representation (left) and its dual, the Belyi triangulation (right.)

The Belyi triangulation can just as easily seen as the kis of the König representation—the König representation is triangulated by placing a new vertex in the center of each face and connecting the new vertex to the old, surrounding vertices with lines.

If the surface is oriented, the Belyi triangulation also has a chess coloring (a proper face 2-coloring). Use the orientation of the surface to color each triangular face + or - according to whether its three vertices run black/white/pink counter-clockwise or clockwise.

The Cori representation is:

C = Me(W),

where the newly referenced map operation is medial, gives a 4-regular map with black, white, and pink regions representing hypervertices, hyperedges, and hyperfaces respectively. Below, the Walsh representation (left) and its medial, the Cori representation (right.)

The Quad representation is:

Q = Ra(W) = Du(Me(W)),

where the newly referenced map operation is radial, which gives a quadrilateral-faced map where each quadrilateral has black and white vertices on one diagonal and pink vertices on the other. The quad representation is dual to the Cori. Below, the Cori representation of a 1-brin on the sphere (left) and its dual, the quad representation (right,) having a single quadrilateral face.