On the uniform generation of modular diagrams

In this paper we present an algorithm that generates $k$-noncrossing, $\sigma$-modular diagrams with uniform probability. A diagram is a labeled graph of degree $\le 1$ over $n$ vertices drawn in a horizontal line with arcs $(i,j)$ in the upper half-plane. A $k$-crossing in a diagram is a set of $k$ distinct arcs $(i_1,j_1),(i_2,j_2),\dots ,(i_k,j_k)$ with the property $i_1 < i_2 < \ldots < i_k < j_1 < j_2 < \ldots< j_k$\mathrm{.}Adiagramwithoutany$k$-crossingsiscalleda$k$-noncrossingdiagramandastackoflength$\sigma$isamaximalsequence$((i,j),(i+1,j-1),\dots,(i+(\sigma-1),j-(\sigma-1)))$\mathrm{.}Adiagramis$\sigma$-modularifanyarciscontainedinastackoflengthatleast$\sigma$\mathrm{.}Ouralgorithmgeneratesafter$O(n^k)$preprocessingtime,$k$-noncrossing,$\sigma$-modulardiagramsin$O(n)$ time and space complexity.