Abstract
Finding a class of structures that is rich enough for adequate linguistic representation yet restricted enough for efficient computational processing is an important problem for dependency parsing. In this paper, we present a transition system for 2-planar dependency trees -- trees that can be decomposed into at most two planar graphs -- and show that it can be used to implement a classifier-based parser that runs in linear time and outperforms a state-of-the-art transition-based parser on four data sets from the CoNLL-X shared task. In addition, we present an efficient method for determining whether an arbitrary tree is 2-planar and show that 99% or more of the trees in existing treebanks are 2-planar.
Introduction
In dependency parsing, syntactic structures are represented as graphs where links (arcs) connect words. A common simplification is projectivity, where dependency links never cross when drawn above the sentence. While projective parsers are computationally efficient (linear time), they fail to capture the "non-projective" structures common in languages with free word order or long-distance dependencies.
The research community faces a trade-off: fast projective parsers with limited representational power versus general non-projective parsers that are often computationally expensive. This paper explores a "mildly non-projective" middle ground: multiplanarity. A structure is $m$-planar if its links can be partitioned into $m$ sets (planes) such that no links within a single plane cross.
Methods
The authors propose two primary algorithmic contributions to leverage 2-planarity.
Determining Multiplanarity
To identify if a tree is $m$-planar, the authors construct a crossings graph. Each dependency link is a node, and edges connect nodes if their corresponding links cross. Determining 2-planarity then reduces to a 2-coloring problem: can nodes be colored "Red" or "Blue" such that no adjacent nodes share a color? This is solvable in linear time using breadth-first search.
The 2-Planar Transition Parser
The proposed parser extends the "arc-eager" transition-based model by incorporating two stacks (active and inactive).
- Mechanism: The parser uses standard transitions (Shift, Reduce, Left-Arc, Right-Arc) on the active stack.
- Innovation: A new
SWITCHtransition swaps the active and inactive stacks. This allows the parser to build one plane of dependencies on Stack A and another on Stack B, handling crossing links while maintaining $O(n)$ complexity.
Results and Analysis
Coverage of 2-Planarity
Analysis across eight language treebanks reveals that 2-planarity is a "sweet spot" for linguistic representation. While 1-planarity (projectivity/planarity) covers only 80-85% of sentences in some languages, 2-planarity covers over 99% across nearly all tested datasets.
As shown in Table 1, even in highly non-projective languages like Czech (23.16% non-projective), only 0.09% of structures fail to meet the 2-planar criteria.
Parsing Performance
The 2-planar parser was evaluated against the MaltParser baseline on four CoNLL-X datasets.
The 2-planar parser consistently outperformed the strictly projective Malt P baseline. Notably, on the Czech dataset, it achieved a 60.7% recall on non-projective arcs (NPR), a significant improvement over projective methods and competitive with complex pseudo-projective post-processing (Malt PP).
Discussion
The results suggest that nearly all human language syntax can be decomposed into two non-crossing layers. The 2-planar parser provides an elegant, single-pass solution that avoids the complexity of pre- and post-processing while remaining linearly efficient.
Future work includes optimizing the "oracle" to better decide when to SWITCH stacks and developing features that specifically track the relationship between the two stacks. While the system could be generalized to $m$ stacks, the 99%+ coverage of 2-planarity suggests diminishing returns for higher values of $m$.
Summary updated