A Decomposition Algorithm for the Oriented Adjacency Graph of the Triangulations of a Bordered Surface with Marked Points

  • Weiwen Gu


In this paper we consider an oriented version of adjacency graphs of triangulations of bordered surfaces with marked points.

We develop an algorithm that determines whether a given oriented graph is an oriented adjacency graph of a triangulation. If a given oriented graph corresponds to many triangulations, our algorithm finds all of them. As a corollary we find out that there are only finitely many oriented connected graphs with non-unique associated triangulations. We also discuss a new algorithm which determines whether a given quiver is of finite mutation type. This algorithm is linear in the number of nodes and is more effective than the previously known one.

Article Number