We investigate a series of graph-theoretic constraints on non-projective dependency parsing and their effect on expressivity, . whether they allow naturally occurring syntactic constructions to be adequately represented, and efficiency, . whether they reduce the search space for the parser. In particular, we define a new measure for the degree of non-projectivity in an acyclic dependency graph obeying the single-head constraint. The constraints are evaluated experimentally using data from the Prague Dependency Treebank and the Danish Dependency Treebank. .
