Combinatorics of double cosets and fundamental domains for the subgroups of the modular group

As noticed by R.~Kulkarni, the conjugacy classes of subgroups of the modular group correspond bijectively to bipartite cuboid graphs. We’ll explain how to recover the graph corresponding to a subgroup $G$ of ${\mathrm{P}\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$ from the combinatorics of the right action of ${\mathrm{P}\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$ on the right cosets $G\mathrm{\backslash }{\mathrm{P}\mathrm{S}\mathrm{L}}_2(\mathbb{Z})$. This gives a method of constructing nice fundamental domains (which Kulkarni calls “special polygons”) for the action of $G$ on the upper half plane. For the classical congruence subgroups ${\mathrm{\Gamma }}_0(N)$, ${\mathrm{\Gamma }}_1(N)$, $\mathrm{\Gamma }(N)$ etc. the number of operations the method requires is the index times something that grows not faster than a polynomial in $\log N$. This is roughly the square root of the number of operations required by the naive procedure. We give algorithms to locate an element of the upper half-plane on the fundamental domain and to write a given element of $G$ as a product of independent generators. We also (re)prove a few related results about the automorphism groups of modular curves. For example, we give a simple proof that the automorphism group of $X(N)$ is ${\mathrm{S}\mathrm{L}}_2(\mathbb{Z}\mathrm{/}N)\mathrm{/}\{\pm I\}$.