In this paper we introduce a new approach to transition-based depen- dency parsing. We propose that the parser construct an undirected graph during the parsing process, instead of a standard directed dependency structure. A pos- teriori, the output undirected structure is converted into a dependency tree. This alleviates error propagation, a characteristic problem of these systems. We apply this approach to obtain undirected variants of the Planar and 2-Planar parsers and of Covington's non-projective parser. We perform experiments on several treebanks from the CoNLL-X shared task, showing that these variants outperform the original directed algorithms in most of the cases.