Existing approaches for graph-based deep dependency parsing that force connexity in predicted graphs do no cover the structures observed in French treebanks. We propose a novel algorithm that covers the full set of possible structures. We evaluate our approach on the French corpora FTB and Sequoia and observe a trade-off between the validity of predicted structures and the quality of predictions