Determining the finite subgraphs of curve graphs (Q1733159)

Let $S=S_{g,n}$ be a surface of genus $g$ and $n$ boundary components, assume that $S$ is not the disc. Let $\mathcal{C}(S)$ be the curve complex of $S$. This is a complex with vertices the isotopy classes of essential simple curves and there is an edge between two vertices if they have minimal intersection number. Moreover, let $\mathcal{P}_{g,n}$ denote the collection of finite induced subgraphs of $\mathcal{C}$. The main theorem is the following: \par Theorem 0.1 There is an algorithm that determines, given a graph $G$ and a pair $(g,n)$, whether or not $G\in \mathcal{P}_{g,n}.$ As a corollary, the authors explore the following problem: given a finite graph $G$ that embeds as a subgraph of $\mathcal{C}$, let $\Gamma(G)$ denote the right angled Artin group determined by $G$. Does $\Gamma(G)$ embed in the mapping class group of \(S\)? A corollary of the main result is that when $S$ is a sphere with at most 5 punctures or a torus with at most 2 punctures there is an algorithm that decides the above question.