$$
$$
In the first post of this series, we saw how graphs and symmetric graphs are \mathsf{C}-sets and how they are implemented in Catlab.jl. Such graphs mildly generalize the concept of graph familiar from combinatorics and computer science. They are preferred by category theorists because every small category has an underlying graph in this sense,1 and so categories can be seen as graphs with composable edges. There is, however, another notion of graph, based on “half-edges” or “darts,” that is popular in parts of physics (Marcolli and Port 2015; Markl, Merkulov, and Shadrin 2009), topological graph theory (Lando and Zvonkin 2004), and computational geometry.
In this post we introduce half-edge graphs and explain their close relation with symmetric graphs. We also show how half-edge graphs lead to “rotation systems,” an important concept of topological graph theory. Rotation systems perfectly capture the combinatorial information associated with a graph embedded in an oriented surface, up to continuous deformation.
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.
| H | vertex | inv |
|---|---|---|
| 1 | 1 | 4 |
| 2 | 2 | 5 |
| 3 | 3 | 6 |
| 4 | 2 | 1 |
| 5 | 3 | 2 |
| 6 | 1 | 3 |
| 7 | 1 | 7 |
| 8 | 1 | 8 |
| 9 | 3 | 9 |
When visualized, the dangling edges are distinguished from the full edges by being incident to a vertex on one side only.
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.2
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,3 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.
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.4 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:
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.5 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.6 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.
The underlying graph of a category has objects as vertices and morphisms as edges, with domains as sources and codomains as targets. Similarly, every groupoid has an underlying symmetric graph with the edge involution given by inverses of morphisms.↩︎
The definition of the pullback functor F^* is incomplete because we have not defined \mathsf{C}-set homomorphisms—morphisms of [\mathsf{C},\mathsf{Set}]—much less how F^* acts on them. The short answer is that \mathsf{C}-set homomorphisms are natural transformations and F^* acts on them by whiskering. We will examine \mathsf{C}-set homomorphisms in a future post.↩︎
This technicality is why symmetric graphs are not quite interchangeable with the graph theorist’s undirected multigraphs.↩︎
The nLab calls this structure a ribbon graph; however, that term seems to be used more often for the geometric realization of a rotation system constructed out of disks and thin bands. Ribbon graphs in this sense are equivalent to band decompositions (Gross and Tucker 1987; Ellis-Monaghan and Moffatt 2013, fig. 1.3).↩︎
Besides being less intuitive, the implicit representation of vertices comes with a cost: vertex attributes, such as coordinates in a surface embedding, cannot be attached directly to a vertex, but must be assigned to all incident half-edges and then asserted equal under the action by \sigma. \mathsf{C}-sets with data attributes will discussed in a future post.↩︎
The symbols “\sigma” and “\alpha” derive from the French words “sommet” (vertex) and “arête” (edge) (Lando and Zvonkin 2004, Remark 1.3.18).↩︎
