A fast algorithm to generate open meandric systems and meanders

Abstract

An open meandric system is a planar configuration of acyclic curves crossing an infinite horizontal line in the plane such that the curves may extend in both horizontal directions. We present a fast, recursive algorithm to exhaustively generate open meandric systems with n crossings. We then illustrate how to modify the algorithm to generate unidirectional open meandric systems (the curves extend only to the right) and nonisomorphic open meandric systems where equivalence is taken under horizontal reflection. Each algorithm can be modified to generate systems with exactly k curves. In the unidirectional case when k = 1, we can apply a minor modification along with some additional optimization steps to yield the first fast and simple algorithm to generate open meanders.