Graphs and C-sets II: Half-edges and rotation systems

Half-edge graphs

A half-edge graph, instead of having edges, has half-edges paired together by an involution. Formally, the schema for half-edge graphs is the category \mathsf{Sch}(\mathsf{HGraph}) generated by the objects and morphisms

subject to the equation \operatorname{inv}^2 = 1_H. A half-edge graph, or \mathsf{Sch}(\mathsf{HGraph})-set, G thus consists of a set of vertices G(V) and a set of half-edges G(H), where each half-edge h \in G(H) is incident to a vertex h \cdot \operatorname{vert}\in G(V) and is paired with another half-edge h \cdot \operatorname{inv}\in G(H) so that h \cdot \operatorname{inv}\cdot \operatorname{inv}= h.

In Catlab, the schema and data type for half-edge graphs are defined as:

@present SchHalfEdgeGraph(FreeSchema) begin
  V::Ob
  H::Ob
  vertex::Hom(H,V)
  inv::Hom(H,H)

  compose(inv, inv) == id(H)
end

@acset_type HalfEdgeGraph(SchHalfEdgeGraph, index=[:vertex])

Many authors call half-edge graphs simply “graphs.” More importantly, some authors insist that the involution on half-edges be fixed-point free: h \cdot \operatorname{inv}\neq h for all h \in G(H). There are two good reasons to drop this restriction. At a technical level, the property of having no fixed points is not algebraic and in particular cannot be expressed in the logic of \mathsf{C}-sets. Also, the half-edges h fixed under the involution, h \cdot \operatorname{inv}= h, have a natural interpretation as dangling edges. These half-edges are not paired with any others and so are left “dangling” at the boundary of the graph. By contrast, distinct half-edges h \neq h' paired under the involution and incident to the same vertex, h \cdot \operatorname{vert}= h' \cdot \operatorname{vert}, are ordinary self-loops.

As with graphs and symmetric graphs, Catlab wraps that the generic \mathsf{C}-sets interface with a simple interface inspired by Graphs.jl. The functions add_edge(s)! add pairs of distinct half-edges, while the functions add_dangling_edge(s)! add half-edges fixed by the involution.

using Catlab.Graphs, Catlab.Graphics

g = HalfEdgeGraph(3)
add_edges!(g, [1,2,3], [2,3,1])
add_dangling_edges!(g, [1,1,3])
g

When visualized, the dangling edges are distinguished from the full edges by being incident to a vertex on one side only.

to_graphviz(g)

Relation with symmetric graphs

Judging by the definitions, half-edge graphs look quite similar to symmetric graphs. We can state the relationship between them very precisely using categorical language. First, some generalities about schema mappings.

If small categories are schemas, then functors between them must be schema mappings; from a slightly different point of view, if categories are theories, then functors are interpretations of one theory in another. Given a small category \mathsf{C}, denote the category of \mathsf{C}-sets as [\mathsf{C},\mathsf{Set}], using a standard notation for functor categories. Any functor F: \mathsf{C} \to \mathsf{D} induces a pullback functor F^*: [\mathsf{D},\mathsf{Set}] \to [\mathsf{C},\mathsf{Set}] sending \mathsf{D}-sets to \mathsf{C}-sets. Specifically, each functor Y: \mathsf{D} \to \mathsf{Set} is mapped to the functor F \operatorname{⨟}Y: \mathsf{C} \to \mathsf{Set}, or pictorially:

In particular, an isomorphism of categories F: \mathsf{C} \cong \mathsf{D} induces an isomorphism F^*: [\mathsf{D},\mathsf{Set}] \cong [\mathsf{C},\mathsf{Set}] between \mathsf{C}-sets and \mathsf{D}-sets.²

Returning to the setting of graphs, define a functor F: \mathsf{Sch}(\mathsf{SGraph}) \to \mathsf{Sch}(\mathsf{HGraph}) by

V \mapsto V, \quad E \mapsto H, \quad \operatorname{src}\mapsto \operatorname{vert}, \quad \operatorname{tgt}\mapsto \operatorname{inv}\operatorname{⨟}\operatorname{vert}, \quad \operatorname{inv}\mapsto \operatorname{inv}.

A short calculation shows that this functor is well-defined, preserving all the equations in \mathsf{Sch}(\mathsf{SGraph}). For example:

F(\operatorname{inv}\operatorname{⨟}\operatorname{tgt}) = F(\operatorname{inv}) \operatorname{⨟}F(\operatorname{tgt}) = \operatorname{inv}^2 \operatorname{⨟}\operatorname{vert}= \operatorname{vert}= F(\operatorname{src}).

The functor is even invertible, with inverse F^{-1}: \mathsf{Sch}(\mathsf{HGraph}) \to \mathsf{Sch}(\mathsf{SGraph}) sending \operatorname{vert} to \operatorname{src}. It is again straightforward to check the necessary equations, such as

F^{-1}(F(\operatorname{tgt})) = F^{-1}(\operatorname{inv}\operatorname{⨟}\operatorname{vert}) = F^{-1}(\operatorname{inv}) \operatorname{⨟}F^{-1}(\operatorname{vert}) = \operatorname{inv}\operatorname{⨟}\operatorname{src}= \operatorname{tgt}.

In conclusion, we have an isomorphism of schemas F: \mathsf{Sch}(\mathsf{SGraph}) \cong \mathsf{Sch}(\mathsf{HGraph}), which induces an isomorphism F^*: \mathsf{HGraph}\cong \mathsf{SGraph}.

So half-edge graphs are isomorphic to symmetric graphs, making the two interchangeable for most purposes, but it is important to realize that the isomorphism is not unique or canonical. The schema for symmetric graphs has an automorphism S: \mathsf{Sch}(\mathsf{SGraph}) \to \mathsf{Sch}(\mathsf{SGraph}) that exchanges \operatorname{src} and \operatorname{tgt} and preserves the other objects and morphisms. Composing this symmetry with F yields another isomorphism S \operatorname{⨟}F: \mathsf{Sch}(\mathsf{SGraph}) \cong \mathsf{Sch}(\mathsf{HGraph}), now sending \operatorname{src} to \operatorname{inv}\operatorname{⨟}\operatorname{vert} and \operatorname{tgt} to \operatorname{vert}. Thus, if you want to interchange symmetric graphs with half-edge graphs, you must say how you’re going to do it.

Even with this caveat, if half-edge graphs are essentially the same as symmetric graphs, why introduce this extra concept? One reason is that that the two concepts have different interpretations. A loop in a symmetric graph can be fixed or not by the edge involution,³ but both cases have the same interpretation, making no reference to dangling edges. Moreover, half-edge graphs are the starting point for a whole line of important structures in topological graph theory and computational geometry.

Rotation systems

Consider a half-edge graph embedded in an oriented surface such as the plane or the sphere. Is there any combinatorial information, besides the graph structure, that is invariant under continuous deformation (orientation-preserving homeomorphism)? Importantly, there is: the cyclic ordering of half-edges incident to each vertex, given by tracing a circle around the vertex according to the local orientation.

This extra information is captured by a rotation system, an important concept of topological graph theory. A graph with a rotation system is a half-edge graph G equipped with a permutation \sigma: G(H) \to G(H) of half-edges, where each cycle of \sigma consists of the half-edges G(\operatorname{vert})^{-1}(v) incident to some vertex v of G.⁴ Graphs with rotation systems are not quite \mathsf{C}-sets, since the constraint on the permutation cycles cannot be expressed, but a slightly more general structure is.

The schema for rotation graphs is the category generated by

subject to the equations \operatorname{inv}^2 = 1_H and \sigma \operatorname{⨟}\operatorname{vert}= \operatorname{vert}. The notation \sigma: H \xrightarrow{\cong} H means that \sigma is an isomorphism, shorthand for introducing another generating morphism \sigma^{-1}: H \to H that obeys the equations \sigma \operatorname{⨟}\sigma^{-1} = 1_H =\sigma^{-1} \operatorname{⨟}\sigma. A rotation graph is then a half-edge graph G with a permutation G(\sigma): G(H) \to G(H) such that half-edges belonging to the same cycle are incident to the same vertex: h \cdot \sigma \cdot \operatorname{vert}= v whenever h \cdot \operatorname{vert}= v. Unlike in a graph with a rotation system, multiple cycles may be incident to the same vertex.

The package CombinatorialSpaces.jl provides combinatorial data structures for geometric objects. It defines the schema for rotation graphs as:

@present SchRotationGraph <: SchHalfEdgeGraph begin
  σ::Hom(H,H)
  
  compose(σ, vertex) == vertex
end

The choice of whether to include the inverse \sigma^{-1} in the schema depends on whether one wants to store and maintain the inverse or compute it on the fly, when needed. Future versions of Catlab may include better builtin support for constraints such as injectivity, surjectivity, and bijectivity.

What if we insist that the schema enforce a one-to-one correspondence between vertices and cycles of the permutation \sigma? We can apply a little trick: if vertices should be identified with cycles of \sigma, then we need not explicitly represent vertices at all. This may seem strange but it is commonplace in data structures for computational geometry.⁵ Specifically, the schema for rotation systems is the category \mathsf{Sch}(\mathsf{RotSys}) generated by

subject to the equation \alpha^2 = 1_H. We follow tradition in writing \alpha for the half-edge involution of a rotation system.⁶ The category \mathsf{Sch}(\mathsf{RotSys}) has only one object, making it a monoid, and every morphism is invertible, so it is even a group. Thus, a rotation system, or \mathsf{Sch}(\mathsf{RotSys})-set, is not just a category action but a group action. In a rotation system, the orbits under \sigma are identified with vertices and the orbits under \alpha with edges. Usually \alpha is required to act freely, thus barring dangling edges. Some authors also insist that the whole group \langle \sigma, \alpha \rangle = \mathsf{Sch}(\mathsf{RotSys}) act transitively, which corresponds to the graph being connected.

Rotation systems are fundamental in topological graph theory because they correspond one-to-one with embeddings of graphs in oriented surfaces, up to equivalence under orientation-preserving homeomorphism (Gross and Tucker 1987, Theorem 3.2.3). This statement has some fine print. First, it refers to cellular embeddings: embeddings of a graph G in a surface S such that every region, or connected component of the complement S \setminus G, is homeomorphic to an open disk. In particular, no nonempty graph can be cellularly embedded in the plane, because the outer region will have a hole. However, cellular embeddings are commonly taken in the sphere, and any spherical embedding can be converted to a planar (noncellular) embedding by stereographic projection. Related to this point, while every rotation system is embeddable in some surface (Mohar and Thomassen 2001, sec. 3.2), not every rotation system defines a planar graph; those that do are planar rotation systems.

In a future post, we will see how rotation systems can be extended to describe surface decompositions and faces of polyhedra.