I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different types of edges (hierarchical, non-hierarchical).I'm new to graph theory and algorithms in general, and I hope that this question doesn't collide e.g. with the research-level requirements of this site. It should however generally be in the scope of cstheory.The graph would have to be drawn bottom-up (I think), as all tokens should be displayed with the same y-coordinate, and the y-coordinates of nodes grouping tokens and/or nodes into constituents will have to be calculated dynamically, e.g., via their longest path to a token.Hierarchical edges (used for grouping tokens/nodes into constituents) should have a minimum number of bendpoints (ideally 0), but there should also be a minimum number of crossings, overwriting the former requirement if needs be.Non-hierarchical edges (used for dependencies) should have a minimum number of crossings, and be drawn as Bzier curves.The next best thing I have come across is the algorithm described by Buchheim et al., improving Walker's algorithm to run in linear time.Please do let me know should there be any need to improve my question, and thanks a lot in advance for any pointers.EDIT:As pointed out in a comment, I should mention that I basically want a default graph layout by an algorithm, which I - in the long run - want to edit and revise within the Eclipse GEF possibilities. I have previously looked into options to get Graphviz to work with GEF, but there seems to be no working solution that preserves all editing functionality inherited from GEF.
Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?
ds.algorithms;graph algorithms;cg.comp geom;graph drawing