Flip Graphs of Convex Polygons

Flip Graphs, are obtained, by considering triangulations on a fixed set of points as vertices, and connect two vertices, if it is possible to get from one triangulation to the other by flipping a single edge.

struct FlipGraphPlanar <: AbstractGraph{Int32}

A Graph representing the FlipGraph of a convex polygon.

Vertices are different triangulations of the same convex polygon.

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

FlipGraphPlanar implements the AbstractGraph interface from Graphs.jl. It is therefore possible to use it with other packages that work with Graphs.jl. This is very helpfull for plotting the graph.


flipgraph(g::TriangulatedPolygon; kwargs..)

Construct the FlipGraph for the TriangulatedPolygon g.


  • 'modular::Bool = false' : by default the whole flip graph is constructed. If modular is set to true, then only the modular flip graph is constructed.

In a modular flip graph, vertices of the FlipGraph are classes of isomorphisms up to renaming the vertices. Each class is then represented by one of its elements.

flipgraph_planar(n::Integer; modular=false) :: FlipGraphPlanar

Construct the FlipGraphPlanar of a convex n-gon.

If modular=true, the FlipGraph is reduced to its modular form.


julia> flipgraph_planar(6)
FlipGraphPlanar with 14 vertices and 21 edges

Graph methods

@docs nv(::FlipGraphPlanar) ne(::FlipGraphPlanar) vertices(::FlipGraphPlanar) edges(::FlipGraphPlanar) has_vertex(::FlipGraphPlanar,v) has_edge(::FlipGraphPlanar,s,d) has_edge(::FlipGraphPlanar,::Edge) neighbors(::FlipGraphPlanar, ::Integer) diameter(::FlipGraphPlanar)