# Modular Flip Graphs of Closed Orientable Surfaces

Contrary to flip graphs of planar triangulations like that of a convex polygon, the flip graph of a closed surface is generally infinitely large. Therefore, it is impossible to construct the whole flip graph. Not only are they infinitely large, but they also "grow" very fast. For this reason, it is more interesting and achievable to look at the **modular flip graphs**. These are graphs whose vertices are homotopy classes of triangulations on closed surfaces.

It turns out that the vertices of modular flip graphs are equivalent to the *Δ-coplexes* which we have already modeled in DeltaComplex.

## Structures

A ** FlipGraph** consists of vertices that represent homotopy classes of

`DeltaComplex`

es and edges between them. In order to be able to efficiently compute the whole flip graph, vertices are not `DeltaComplex`

es but have their own structure (`FGVertex`

) which consists of a `DeltaComplex`

with additional information.`FlipGraphs.FlipGraph`

— Type`struct FlipGraph <: AbstractGraph{Int}`

A *graph* representing the **flip graph** of a **Δ-Complex**.

Vertices are isotopy classes of triangulations of the same surface.

Two vertices are linked by an edge, if the respective triangulations differ only by a single flip.

`FlipGraphs.FGVertex`

— Type`struct FGVertex`

A *vertex* in a `FlipGraph`

.

A `FGVertex`

is composed of a representant (`DeltaComplex`

) of the isotopy class of that vertex. The representant has been relabeled with one of the canonical labeling obtained by an adaptation of *McKay's Algorithm*. Additionally, the `FGVertex`

contains the number of labeling that are output by the respective *McKay's Algorithms*.

## Constructors

Currently, it is only possible to create the modular flip graph of a closed *orientable* surface. Non-orientable surfaces would need an adapted approach to solving, as the way they are modeled right now would require a lot more options to be checked just to determine if two `DeltaComplex`

es are isomorphic to each other.

As even modular flip graphs become very large quite quickly, you have the possibility of only building a local portion of a flip graph. The way this works is, by giving it a `DeltaComplex`

, which forms the root vertex, and setting the `depth`

, which will limit the vertices to only include those that are at a distance less or equal to this `depth`

from the root.

`FlipGraphs.flipgraph_modular`

— Function`flipgraph_modular(g::Integer, p::Integer; kwargs..) :: FlipGraph`

Construct the **modular flip graph** for a genus `g`

closed orientable surface with `p`

points on it.

**Arguments**

`labeled_points :: Bool = true`

: If set to`false`

, the isomorphism also includes a renaming of the points.

`flipgraph_modular(D::DeltaComplex; kwargs..)`

Construct the **modular flip graph** for the closed orientable surface defined by the *Δ-complex* `D`

.

**Arguments**

`labeled_points :: Bool = true`

: If is set to`false`

, then the isomorphism also includes a renaming of the points.`depth :: Integer = ∞`

: Determines the depth to which the flip grap should be constructed. i.e. up to which distance from`D`

.

## Graph methods

As with `FlipGraphPlanar`

, there are a bunch of methods which overload some of the main functions from the Graphs.jl package.

`Graphs.nv`

— Method`nv(G::FlipGraph) :: Int`

Return the number of vertices in `G`

.

`Graphs.ne`

— Method`ne(G::FlipGraph) :: Int`

Return the number of edges in `G`

.

`Graphs.vertices`

— Method`vertices(G::FlipGraph) :: Vector{FGVertex}`

Return the list of all the vertices that have been constructed in `G`

.

`FlipGraphs.vertices_deltacomplex`

— Function`vertices_deltacomplex(G::FlipGraph) :: Vector{DeltaComplex}`

Construct a list of all the `DeltaComplex`

s which form the vertices in `G`

.

`Graphs.edges`

— Method`edges(G::FlipGraph) :: Vector{Edge}`

Construct a list containing all the edges in `G`

.

`Graphs.has_vertex`

— Method`has_vertex(G::FlipGraph, v::Integer) :: Bool`

Return true if `v`

is a valid index of a vertex in `G`

.

`FlipGraphs.get_vertex`

— Method`get_vertex(G::FlipGraph, id::Integer) :: Vector{FGVertex}`

Return the `id`

-th vertex the flip graph `G`

.

`Graphs.has_edge`

— Method`has_edge(G::FlipGraph, e::Edge) :: Bool`

Return `true`

if `e`

is an edge in `G`

.

`Graphs.has_edge`

— Method`has_edge(G::FlipGraph, s::Integer, d::Integer) :: Bool`

Return `true`

if there is an edge between the `s`

-th and `d`

-th vertex in `G`

.

`Graphs.has_edge`

— Method`has_edge(G::FlipGraph, v1::FGVertex, v2::FGVertex) :: Bool`

Return `true`

if there is an edge between `v1`

and `v2`

in `G`

.

`Graphs.neighbors`

— Method`neighbors(G::FlipGraph, v::Integer) :: Vector{Int32}`

Return a list of the indices of all the neighboring vertices of the `v`

-th vertex.

`FlipGraphs.diameter`

— Method`diameter(G::FlipGraph)`

Compute the diameter of the `FlipGraph`

`G`

.

## Comparing Triangulations

One problem in deciding if two triangulations are equivalent, is that the naming of the vertices, edges and points is completely arbitrary. In the act of flipping, `DualEdge`

s and `TriFace`

s "move around". It is therefore possible to obtain two `DeltaComplex`

es representing the same triangulation of a surface but with different labeled `TriFace`

s and `DualEdge`

s.

The following method will determine if two `DeltaComplex`

es are isomorphic to each other and therefore represent the same vertex in the modular flip graph:

`FlipGraphs.is_isomorphic`

— Method`is_isomorphic(D1::DeltaComplex, D2::DeltaComplex; kwargs..) :: Bool`

Return `true`

if `D1`

is isomorph to `D2`

up to a renaming of the vertices, edges and if `labeled_points=false`

also points.

**Arguments**

`labeled_points :: Bool = true`

: If labeled_points is set to`false`

, then the isomorphism also includes a renaming of the points.

## Canonical labeling of `DeltaComplex`

es

Checking every possible permutation of `TriFace`

and `DualEdge`

labeling was not an option, as the number of possibilities would blow up immediately.

What one can do instead is try to find a canonical labeling. This module uses a version of *McKay's canonical graph labeling algorithm*^{[1]} to try and determine a unique labeling based on the relationship of vertices and edges to other vertices and edges. In general, it is not always possible to determine a unique labeling. However, with this method, we can reduce the number of labelings to a manageable number.

The `mcKay`

methods each return a permutation vector `p`

which can be interpreted as a Cauchy's one-line notation for permutations. For example, `p = [3,5,1,2,6,4]`

would correspond to the following permutation:

\[σ = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} = (1\ 3)(2\ 5\ 6\ 4)\]

This algorithm has been adapted to find canonical labelings for points, vertices and edges. These are not independent from each other. In fact, only the point labelings depend on themselves. mcKay*vertices will give different results basedon the point labelings, and mcKay*edges will give different results based on both point and vertex labelings. Therefore, they are to be used in sequence.

`FlipGraphs.mcKay_points`

— Function`mcKay_points(D::DeltaComplex; kwargs..) :: Vector{Vector{Int32}}`

Apply a version of McKay's canonical graph labeling algorithm to determine all possible permutations of the points which give a canonical isomorphism class representant.

Return a vector of permutation vectors `p`

such that point 1 becomes point `p[1]`

, point 2 becomes point `p[2]`

,...

**Arguments**

`only_one :: Bool = false`

, If set to true, the algorithm will stop after finding a single valid permutation.

`FlipGraphs.mcKay_vertices`

— Function`mcKay_vertices(D::DeltaComplex; , A_deltacomplex::Matrix{<:Integer}, point_perm::Vector{<:Integer}) :: Vector{Vector{Int32}}`

Apply a version of McKay's canonical graph labeling algorithm in order to determine all possible permutations of the `TriFace`

s which give a canonical isomorphism class representant.

Return a vector of permutation vectors `p`

such that `TriFace`

1 becomes `TriFace`

`p[1]`

, `TriFace`

2 becomes `TriFace`

`p[2]`

, ...

If `only_one=true`

, the algorithm stops after finding one valid permutation.

The vectors `point_perm`

determins how the points of `D`

are implied to have been renamed, without actually having been changed.

`mcKay_vertices(D::DeltaComplex; kwargs..) :: Vector{Vector{Int32}}`

Apply a version of McKay's canonical graph labeling algorithm in order to determine all possible permutations of the `TriFace`

s which give a canonical isomorphism class representant.

Return a vector of permutation vectors `p`

such that `TriFace`

1 becomes `TriFace`

`p[1]`

, `TriFace`

2 becomes `TriFace`

`p[2]`

, ...

If `only_one=true`

, the algorithm stops after finding one valid permutation.

**Arguments**

`only_one :: Bool = false`

, If set to true, the algorithm will stop after finding a single valid permutation.- A_deltacomplex :: Matrix{<:Integer} = Matrix{Int32}(multi
*adjacency*matrix_deltacomplex(D)). If provided, the algorithm will use the adjacency matrix of the`DeltaComplex`

`D`

. If not, the algorithm would have to compute it itself.

`FlipGraphs.mcKay_edges`

— Function`mcKay_edges(D::DeltaComplex; kwargs..) :: Vector{Vector{Int32}}`

Apply McKay's canonical graph labeling algorithm in order to determine all possible permutations of the `DualEdge`

s which give a canonical isomorphism class representant.

Return a vector of permutation vectors `p`

such that `DualEdge`

1 becomes `DualEdge`

`p[1]`

, `DualEdge`

2 becomes `DualEdge`

`p[2]`

, ...

**Arguments**

`only_one :: Bool = false`

, If set to true, the algorithm will stop after finding a single valid permutation.

- 1Hartke, S.G., & Radcliffe, A.J. (2008). McKay ’ s Canonical Graph Labeling Algorithm.