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

Abstract

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.