To the first question "Is the depicted dependency structure plausible at all?", one would have to answer: "That depends on the type of dependency grammar one employs". Kuhlmann, the author of the cited paper, uses a ("mildly") non-projective dependency grammar.
"Non-projective" (aka "discontinuous") is any (sub-)tree structure when a dependency edge (the arrows that connects nodes as in the picture above) crosses over a projection edge (the vertical dotted edge in picture above). This property has been discussed at length within the dependency grammar literature. Please see the Wikipedia page on this topic [https://en.wikipedia.org/wiki/Discontinuity_%28linguistics%29].
Usually non-projectivity (aka discontinuity) arises when the dependency grammar views dependency basically as "government". In the next example
Wem hat er geholfen?
whom has he helped
the question word Wem is governed by geholfen, rather than by hat. A government-based dependency grammar will then connect Wem and "geholfen*, which results in a non-projective structure because the dependency edge connecting Wem and geholfen will cross the projection edge of hat (and that of er).
A number of dependency grammarians regard the limitation on government as too restrictive, and they view the apparent non-projective dependent node (Wem in the above example) as somehow displaced. My own take on this phenomenon can be found here. That paper also contains references to other authors within the dependency grammar framework.
In a projective dependency grammar, such as the one I prefer, the depicted structure is not possible. Rather the nodes Piet and Marie would attach, i.e. be connected via a dependency edge, to the highest verb node, namely zag. Such a constellation is licit under the following condition:
Rising
A node A may be immediately dependent to another B, even though B doesn't govern A, if B dominates the node C, the governor of A.
In my example, Wem = A, hat = B, and geholfen = C. Since B hat dominates geholfen, Wem may rise in order to connect to hat. There are a number of constructions that elicit rising, but they have different syntactic properties.
[I'd also like to emphasize that I believe that the depicted tree structure is inaccurate even on a purely non-projective approach. Piet is governed by zag, in a specific construction that requires an infinitive verb, here helpen. Hence Piet is not a dependent of helpen. The same holds for Marie, which must be a dependent of helpen, rather than of lezen. In non-projective systems, semantics sometimes occludes the appropriate syntactic relationships.]
The answer to the second question, i.e. "What would be appropriate edge labels?", must first decide on whether the apparatus is projective or non-projective. If it is non-projective, standard (i.e. government) labels are in order. In the Dutch example, Marie would be the indirect object of helpen, and Piet the direct object of zag (rather than the subject of helpen).
A projective account can choose whether it wants the labels to reflect the actual dependency connections, or the underlying government relationships (which for the most part are identical; only in examples as the ones used here does a difference appear).
Yet another aspect is whether the grammar is mono- or multistratal. If the grammar is multistratal, i.e. employs more than one level of description, then labels may be transferred from one level to the next higher one. Or such a grammar may choose to use different sets of labels depending on the strata it uses at a specific moment.
If the depicted tree structure were correct (which it isn't as I argued above), the labels for all three nominals, i.e. Jan, Piet, and Marie, would have to be [subject], and obviously that cannot be true because the verbs helpen and lezen are infinitive forms, and infinitives cannot command subjects.
I hope that helps a bit.
