String-to-graph parsing is very closely related to the so-called problem of dependency semantic parsing, where one is given an ordered sequence of vertices and has to output a maximum weight graph defined over those vertices, representing a most-likely semantic analysis of the associated sentence.
with string-to-graph parsing, dependency semantic parsing does not require any hardwired input grammar generating a set of valid graphs.