Hi! That's an interesting use case 
How you set up an annotation workflow kinda depends on the specifics of your dependency scheme. If you can narrow down the possible candidates that are part of a relationship you could stream in pairs and then use the choice interface to select the relationships between them. For instance, if you have an entity recognizer or rule-based process that extracts names and two people are mentioned together, you can show both mentions, and select a label for the relation.
A similar(ish) use case came up in the following thread the other day and it inspired me to dig a bit deeper and try out some ideas we've had for a manual interface for labelling complex relationships, and even relationships and spans at the same time. You can see some early screenshots here:
It turned out to be a really powerful interface and we'll be introducing it in Prodigy v1.10, along with some recipes for fully manual relation annotation, model-assisted dependency parsing annotation and coreference resolution. So this is probably also going to be a good fit for what you're trying to do.