2
$\begingroup$

I came across a problem where I need to be able to find automorphisms of a directed graph embedded on a surface. WLOG, I can assume the surface is a plane (if that is helpful).

Normally, a graph automorphism of a simple graph can be seen as a permutation of the vertices (and that information is sufficient to encode the automorphism). If there are parallel edges, the additional information of edge permutation may be necessary to make an automorphism well-defined. This is true for directed graphs as well. From what I can tell, in the cases directed, no self-loops graphs, this method extends to graphs embedded in the plane/in a surface. What is key is that each automorphism respects orientation and the embedding into the plane.

However, consider the case of self-loops. Then, the information of vertex permutation and edge permutation is not enough to determine an automorphism. Take for example this image: enter image description here

We could send everything to itself via the identity permutation, but that might not preserve the orientation!

To make this clearer, I include an example with an undirected plane graph. enter image description here Here, \phi (a permutation of the vertices) along with the original embedding completely define a graph automorphism (which I'll also call \phi).

Is there a graph theoretic way to describe an automorphism of a directed surface graph such that the automorphism plays well with the topology of the surface and preserves orientation of edges?

Many thanks!

$\endgroup$
6
  • $\begingroup$ Nitpick: an automorphism of the graph is by definition specified by the permutation of vertices and edges, because that information is all there is in the definition of a graph. What you mean is an automorphism of the embedding. Actually possibly helpful remark: this issue is not unique to directed graphs or to graphs with loops. Already with simple undirected graphs you can have multiple embeddings; see this example, for instance. $\endgroup$ Commented Apr 30, 2021 at 14:14
  • $\begingroup$ Although the "graph theorists" definition of a graph uses just an abstract set of vertices and edges and an abstract incidence relation, there are enhanced definitions of graphs which encode more of the topological information. For example, are you familiar with $\Delta$-complexes, as used in Hatcher's "Algebraic Topology"? $\endgroup$
    – Lee Mosher
    Commented Apr 30, 2021 at 15:08
  • $\begingroup$ I think what you might be looking for are "combinatorial maps." There are two parts to this: (1) every edge has two ends, called "darts," and (2) every vertex comes with a cyclic ordering of the incident darts. You can think of a directed graph as being a choice of a distinguished dart per edge. This is also known as a "directed ribbon graph." $\endgroup$ Commented Apr 30, 2021 at 17:56
  • $\begingroup$ Thank you all for the speedy responses! @MishaLavrov I believe I understand that automorphisms of planar graphs may not be automorphisms of plane graphs. I included a picture in the original post to clarify my question. Thank you! $\endgroup$
    – Atrebor
    Commented May 1, 2021 at 15:12
  • $\begingroup$ @LeeMosher I have covered some of the material in Hatcher. Is there a particular section dealing with delta-complexes that could help with this problem? Thank you so much. $\endgroup$
    – Atrebor
    Commented May 1, 2021 at 15:12

1 Answer 1

2
$\begingroup$

The concept of a "ribbon graph" mentioned in the comments, also known as a "fatgraph" is very helpful in this regard. I'll use the "fatgraph" terminology because I'm more familiar with it (I learned it through my contemporary Bob Penner).

Roughly speaking, a fatgraph is a graph $G$ together with enough extra combinatorial data to determine an embedding of $G$ into a compact, oriented surface-with-boundary $S$ such that $G$ is a deformation retract of $S$. One can cap off the boundary circles of $S$, attaching a disc to each, to obtain a closed oriented surface $\widehat S$. In general $\widehat S$ can have any genus, and I'll explain how the genus is calculated. For purposes your question we can specialize to the case that $\widehat S$ has genus $0$, which is to say that $\widehat S$ is (homeomorphic to) the sphere.

Here are some details.

Graphs: First, regarding the definition of a graph, I am going to give the topological definition (what I am describing here is a "1-dimensional $\Delta$-complex", equivalently a "1-dimensional CW-complex", although following topological terminology I am just going to call this a graph).

A finite graph $G$ is a topological space together with a finite indexed subset $V = \{v_i \mid i \in I\} \subset G$ of vertices, such that the following hold:

  1. The complement $G-V$ consists of finitely many components called open edges which are indexed as $E = \{e_j \mid j \in J\}$.
  2. Associated to each open edge $e_j$ is a characteristic map $\chi_j : [0,1] \to G$ such that $\chi_j(0),\chi_j(1) \in V$ and such that $\chi_j \mid (0,1) \to e_j$ is a homeomorphism.
  3. The topology on $G$ is the weakest topology such that each $\chi_j$ is continuous.

For each open edge $e_j$, its closure $\overline e_j \subset G$ is equal to the image $\chi_j[0,1]$. If $\chi_j(0)=\chi_j(1)$ then one gets a loop edge, otherwise one gets a nonloop edge. One effect of assigning an indexing $\{e_j \mid j \in J\}$ and characteristic maps $\chi_j$ is that the different edges are now all distinguishable, regardless of whether they are loop edges or not, and moreover the two "halves" of an edge are also distinguishable, in particular the two halves of a loop are are distinguishable from each other.

Define a half-edge of $G$ to be a subset of the form $\chi_j[0,1/2]$ or of the form $\chi_j[1/2,1]$, for some $j \in J$. Let $D_j$ denote the set of half-edges that contain $v_j$; I think of these intuitively as the "directions" at $v$. The valence of a vertex $v_j \in V$ is the cardinality of the set $D_j$ which I'll denote as $|D_j|$.

In your example there are seven vertices $v_1,v_2,v_3,v_4,v_5,v_6,v_7$ with valences $|D_1|=2$, $|D_2|=4$, $|D_3|=2$, $|D_4|=3$, $|D_5|=2$, $|D_6|=2$, $|D_7|=3$. Your edges aren't indexed, but there are no loop edges, so I can unambiguously label the edges with double subscripts referring to the endpoints $e_{12}$, $e_{17}$, $e_{23}$ (in the presence of loop edges it would be best to use an entirely independent system of indexing $\{e_j \mid j \in J\}$ as above). For any doubly subscripted edge $e_{ii'}$ I'll denote its two half-edges a $d_{ii'}$ (which is a direction at the vertex $v_i$) and $d_{i'i}$ (which is a direction at the vertex $v_i'$). Thus for example we have $$D_1 = \{d_{12},d_{17}\}, D_2 = \{d_{21},d_{23},d_{24},d_{27}\} $$

Fatgraphs: A fatgraph structure on $G$ consists of a choice of cyclic permutation on each direction set $D_j$ ($j \in J$).

In your example, I'll choose the permutation on $D_j$ to be the counterclockwise permutation, which I'll write in cycle notation: \begin{align*} D_1 &= (d_{12},d_{17}) \\ D_2 &= (d_{21},d_{27},d_{24},d_{23}) \\ D_3 &= (d_{32},d_{34}) \\ D_4 &= (d_{42},d_{45},d_{43}) \\ D_5 &= (d_{54},d_{56}) \\ D_6 &= (d_{64},d_{67}) \\ D_7 &= (d_{71},d_{76},d_{72}) \end{align*}

Attaching circuits: Given a fatgraph structure on $G$, here's how you construct the associated embedding of $G$ into a compact, oriented surface with boundary $S$. I'll describe a collection of circuits in $G$ which, in totality, cross every edge exactly twice. To each of these circuits one attaches an annulus, and the quotient space of $G$ and the attached annuli is the surface $S$. So I'll refer to these circuits as the attaching circuits. The whole set of attaching circuits is determined by the given fatgraph structure, and in fact can be very simply computed directly from the fatgraph structure.

A typical attaching circuit is described combinatorially as a cyclic sequence of the form

  • vertex, direction, edge, direction, vertex, direction, edge, direction, vertex, direction, edge, direction,...,

which continues around until you start repeating. More specifically, an attaching circuit has the form $$v_{i(1)}, \, d_{i(1)}^+, \, e_{j(1)}, \, d_{i(2)}^-, \, v_{i(2)}, \, d_{i(2)}^+, \, e_{j(2)}, \, ...\, , \, v_{i(K)}, \, d_{i(K)}^+, \, e_{j(K)}, \, d_{i(K+1)}^- \, = \, d_{i(1)}^- $$ and must satisfy the following constraints:

  • For each $k=1,...,K$ modulo $K$, the two directions $d_{i(k)}^+,d_{i(k+1)}^-$ must be the two half-edges of the edge $e_{j(k)}$
  • For each $k=1,...,K$, the direction $d_{i(k)}^+$ at $v_{i(k)}$ must be the next one in cyclic order after $d_{i(k)}^-$.

The choice of the first vertex $v_{i(1)}$ and the first direction $d_{i(1)}^+ \in D_{i(1)}$ determines the rest of the attaching circuit: $e_{j(k)}$ is the unique edge contining the half edge $d_{i(k)}^+$; $d_{i(k+1)}^-$ is the opposite half of $e_{j(k)}$; $v_{i(k+1)}$ is the vertex containing $d_{i(k+1)}^-$; and $d_{i(k+1)}^+$ is the next direction in cyclic order around $v_{j(k+1)}$ from $d_{i(k+1)}^-$.

In your example, there are four attaching circuits altogether, arising from: the two triangles; the pentagon; and the "outside heptagon".

The attaching circuit corresponding to the triangle with vertices $v_1,v_2,v_7$ is $$v_1, d_{12}, e_{12}, d_{21}, d_{27}, e_{27}, d_{72}, d_{71}, e_{17}, d_{17} $$ where $d_1^+ = d_{12}$, $d_2^- = d_{21}$, and so on.

Genus: Given a fatgraph $G$, as said one embeds $G$ as a deformation retraction of the oriented surface-with-boundary $S$ by attaching one annulus per attaching circuit in $G$. The number of boundary components of $S$ is equal to the number of attaching circuits. One then obtains a closed surface that I'll denote $\widehat S$, by attaching a disc to each boundary circle of $S$, thereby obtaining a pair of embeddings $$G \hookrightarrow S \hookrightarrow \widehat S $$ The genus of $G$ is defined to be the genus of the closed surface $\widehat S$ (I just realized there is a hidden assumption, namely that $G$ is connected, hence $S$ and $\widehat S$ are connected).

In your example, of course, $\widehat S$ is homeomorphic to the 2-sphere, which has genus $0$.

An essential point here is that the genus is completely determined by the Euler characteristic formula \begin{align*} 2-2g = \chi &= \#\text{Vertices} - \#\text{Edges} + \#\text{Faces} \\ &= \#\text{Vertices} - \#\text{Edges} + \#\text{Attaching Circuits} \end{align*} and so \begin{align*} g &= \frac{1}{2} \bigl(2 - \#\text{Vertices} + \#\text{Edges} - \#\text{Attaching Circuits} \bigr) \end{align*} In your example we have (no surprise) $$g = \frac{1}{2} (2 - 7 + 9 - 4) = 0 $$

Isomorphisms: But perhaps even more essential to your question is that in the case of genus 0, the embedding $G \hookrightarrow \widehat S$, not only is determined by the given fatgraph structure, but it determines the fatgraph structure.

To put this more rigorously, consider two fatgraph structures of genus $0$ on the same connected finite graph $G$. These two structures determine two embeddings $$G \hookrightarrow S_1 \hookrightarrow \widehat S_1 $$ and $$G \hookrightarrow S_2 \hookrightarrow \widehat S_2 $$ We may conclude that these two embeddings extend to an orientation preserving homeomorphism $\widehat S_1 \mapsto \widehat S_2$ if and only if the two given fatgraph structures on $G$ are identical, meaning that for each vertex $v_i \in G$, the cyclic permutation on the direction set $D_i$ coming from the first fatgraph structure is identical to the cyclic permutation on $D_i$ coming from the second fatgraph structure.

For example, if you take the fatgraph structure described above that comes from the graph in your post, but then you alter that structure by reversing the cyclic permutations on $D_2$ and $D_7$, then you will get the distinct embedding that one can see in the second diagram of this answer by @MishaLavrov

One can go still further and consider extending the embeddings $G \hookrightarrow \widehat S_1$, $G \hookrightarrow \widehat S_2$ to an orientation reversing homeomorphism $\widehat S_1 \mapsto \widehat S_2$. So for example if you reverse all cyclic permutations of your example then you get the third diagram of the above linked answer.

And in actuality there's nothing special about genus $0$ in this regard: fatgraph structures on $G$ encode all embeddings $G \hookrightarrow F$ into surfaces $F$ such that $F-G$ is a union of open discs.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .