Theorem 1 For noncrossing dependency graphs, Maximum Subgraph can be solved in time O.jV j 3 /.
in this paper we therefore address maximum acyclic subgraph parsing under the restriction that the subgraph should be noncrossing, which informally means that its arcs can be drawn on the half-plane above the sentence in such a way that no two arcs cross (and without changing the order of the words).