  We present a bracketing-based encoding that can be used to represent any
2-planar dependency tree over a sentence of length n as a sequence of n labels,
hence providing almost total coverage of crossing arcs in sequence labeling
parsing. First, we show that existing bracketing encodings for parsing as
labeling can only handle a very mild extension of projective trees. Second, we
overcome this limitation by taking into account the well-known property of
2-planarity, which is present in the vast majority of dependency syntactic
structures in treebanks, i.e., the arcs of a dependency tree can be split into
two planes such that arcs in a given plane do not cross. We take advantage of
this property to design a method that balances the brackets and that encodes
the arcs belonging to each of those planes, allowing for almost unrestricted
non-projectivity (round 99.9% coverage) in sequence labeling parsing. The
experiments show that our linearizations improve over the accuracy of the
original bracketing encoding in highly non-projective treebanks (on average by
0.4 LAS), while achieving a similar speed. Also, they are especially suitable
when PoS tags are not used as input parameters to the models.
