This paper presents a method for non-projective dependency parsing using spanning tree algorithms. The authors formalize weighted dependency parsing as searching for maximum spanning trees (MSTs) in directed graphs. Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n³) time. More surprisingly, the representation is extended naturally to non-projective parsing using the Chu-Liu-Edmonds (CLE) MST algorithm, yielding an O(n²) parsing algorithm. The authors evaluate these methods on the Prague Dependency Treebank using online large-margin learning techniques and show that MST parsing increases efficiency and accuracy for languages with non-projective dependencies. Dependency parsing has seen increased interest for applications such as relation extraction, machine translation, synonym generation, and lexical resource augmentation. The primary reason for using dependency structures instead of more informative lexicalized phrase structures is that they are more efficient to learn and parse while still encoding much of the predicate-argument information needed in applications. Dependency representations, which link words to their arguments, have a long history. The tree in Figure 1 is projective, meaning that if we put the words in their linear order, preceded by the root, the edges can be drawn above the words without crossings. In English, projective trees are sufficient to analyze most sentence types. However, there are certain examples in which a non-projective tree is preferable. For instance, in the sentence "John saw a dog yesterday which was a Yorkshire Terrier," the relative clause and the object it modifies are separated by an adverb. There is no way to draw the dependency tree for this sentence in the plane with no crossing edges. In languages with more flexible word order than English, such as German, Dutch, and Czech, non-projective dependencies are more frequent. Rich inflection systems reduce reliance on word order to express grammatical relations, allowing non-projective dependencies that we need to represent and parse efficiently. A non-projective example from the Czech Prague Dependency Treebank is also shown in Figure 2. Most previous dependency parsing models have focused on projective trees, including the work of Eisner (1996), Collins et al. (1999), Yamada and Matsumoto (2003), Nivre and Scholz (2004), and McDonald et al. (2005). These systems have shown that accurate projective dependency parsers can be automatically learned from parsed data. However, non-projective analyses have recently attracted some interest, not only for languages with freer word order but also for English. The main idea of our method is that dependency parsing can be formalized as the search for a maximum spanning tree in a directed graph. This formalization generalizes standard projective parsing models based on the Eisner algorithm to yield efficient O(n²) exact parsing methods for non-projective languages like Czech. Using this spanning tree representation,This paper presents a method for non-projective dependency parsing using spanning tree algorithms. The authors formalize weighted dependency parsing as searching for maximum spanning trees (MSTs) in directed graphs. Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n³) time. More surprisingly, the representation is extended naturally to non-projective parsing using the Chu-Liu-Edmonds (CLE) MST algorithm, yielding an O(n²) parsing algorithm. The authors evaluate these methods on the Prague Dependency Treebank using online large-margin learning techniques and show that MST parsing increases efficiency and accuracy for languages with non-projective dependencies. Dependency parsing has seen increased interest for applications such as relation extraction, machine translation, synonym generation, and lexical resource augmentation. The primary reason for using dependency structures instead of more informative lexicalized phrase structures is that they are more efficient to learn and parse while still encoding much of the predicate-argument information needed in applications. Dependency representations, which link words to their arguments, have a long history. The tree in Figure 1 is projective, meaning that if we put the words in their linear order, preceded by the root, the edges can be drawn above the words without crossings. In English, projective trees are sufficient to analyze most sentence types. However, there are certain examples in which a non-projective tree is preferable. For instance, in the sentence "John saw a dog yesterday which was a Yorkshire Terrier," the relative clause and the object it modifies are separated by an adverb. There is no way to draw the dependency tree for this sentence in the plane with no crossing edges. In languages with more flexible word order than English, such as German, Dutch, and Czech, non-projective dependencies are more frequent. Rich inflection systems reduce reliance on word order to express grammatical relations, allowing non-projective dependencies that we need to represent and parse efficiently. A non-projective example from the Czech Prague Dependency Treebank is also shown in Figure 2. Most previous dependency parsing models have focused on projective trees, including the work of Eisner (1996), Collins et al. (1999), Yamada and Matsumoto (2003), Nivre and Scholz (2004), and McDonald et al. (2005). These systems have shown that accurate projective dependency parsers can be automatically learned from parsed data. However, non-projective analyses have recently attracted some interest, not only for languages with freer word order but also for English. The main idea of our method is that dependency parsing can be formalized as the search for a maximum spanning tree in a directed graph. This formalization generalizes standard projective parsing models based on the Eisner algorithm to yield efficient O(n²) exact parsing methods for non-projective languages like Czech. Using this spanning tree representation,