Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system? 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 Bézier 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.
you seem to want the following


a graph layout algorithm. many std algorithms typically use force-based methods where nodes are connected by replusive/attractive "springs" and the equilibrium/low energy state is obtained through some amt of iteration (of the corresponding globally-constructed force-related differential equation). the output of the algorithm is a set of 2-d or 3-d coordinates for nodes and (usually) edges.
ability to hand-modify the results of that algorithm. typically called a "graph editor". this starts with the coordinates from the layout algorithm and allows adjustment.


re (1) the forefront software seems to be graphviz. re (2) see eg this question "what is the best graph editor" on mathoverflow.

browsing the graphviz gallery, here are two graph types similar to what you want. 

ER diagram and traffic light. 

you say you have two types of edges. a simple way would be to have directed edges "toward or away" as in the traffic light example. or the edges can be labelled in two ways as in the ER diagram. both examples show two different node types using different shapes or labels, or shading etc. other approaches would be to use coloring.

as the mathoverflow Q/As indicate there are many graph editors. the std one with graphviz is "dotty". see eg pdf "editing graphs with dotty" by Koutsofious.

another technique for graphing, possibly large graphs, is to look at structural compositions eg clique decompositions.