The paper presents a novel approach to dependency parsing by formalizing it as the search for maximum spanning trees (MSTs) in directed graphs. This representation generalizes the Eisner algorithm for projective parsing to non-projective languages using the Chu-Liu-Edmonds MST algorithm, achieving an $O(n^2)$ parsing complexity. The method is evaluated on the Prague Dependency Treebank using online large-margin learning techniques, demonstrating improved efficiency and accuracy for languages with non-projective dependencies. The paper also discusses the advantages of this approach over traditional lexicalized phrase structure methods and provides experimental results showing that the non-projective model outperforms the projective model on the Prague Dependency Treebank.The paper presents a novel approach to dependency parsing by formalizing it as the search for maximum spanning trees (MSTs) in directed graphs. This representation generalizes the Eisner algorithm for projective parsing to non-projective languages using the Chu-Liu-Edmonds MST algorithm, achieving an $O(n^2)$ parsing complexity. The method is evaluated on the Prague Dependency Treebank using online large-margin learning techniques, demonstrating improved efficiency and accuracy for languages with non-projective dependencies. The paper also discusses the advantages of this approach over traditional lexicalized phrase structure methods and provides experimental results showing that the non-projective model outperforms the projective model on the Prague Dependency Treebank.