<p>you seem to want the following</p>

<ul>
<li>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.</li>
<li>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.</li>
</ul>

<p>re (1) the forefront software seems to be <b>graphviz</b>. re (2) see eg this question <a href="https://mathoverflow.net/questions/15664/what-is-the-best-graph-editor-to-use-in-your-articles">"what is the best graph editor" on mathoverflow</a>.</p>

<p>browsing the <a href="http://www.graphviz.org/Gallery.php" rel="nofollow noreferrer">graphviz gallery,</a> here are two graph types similar to what you want. </p>

<p><a href="http://www.graphviz.org/content/ER" rel="nofollow noreferrer">ER diagram</a> and <a href="http://www.graphviz.org/content/traffic_lights" rel="nofollow noreferrer">traffic light</a>. </p>

<p>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.</p>

<p>as the mathoverflow Q/As indicate there are many graph editors. the std one with graphviz is "dotty". see eg pdf <a href="http://www.graphviz.org/pdf/dottyguide.pdf" rel="nofollow noreferrer">"editing graphs with dotty"</a> by Koutsofious.</p>

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

CC BY-SA 3.0
2012-07-18T15:06:07.817Z
2012-07-18T15:18:46.927Z
2017-04-13T12:57:54.777Z
vzn
<p>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).</p>

<p>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. <a href="https://cstheory.meta.stackexchange.com/questions/1541/are-graph-visualisation-algorithm-questions-in-the-scope-of-cstheory-stackexchan">It should however generally be in the scope of cstheory</a>.</p>

<p>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.</p>

<p>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.</p>

<p>Non-hierarchical edges (used for dependencies) should have a minimum number of crossings, and be drawn as Bézier curves.</p>

<p>The next best thing I have come across is the algorithm described by <a href="http://dirk.jivas.de/papers/buchheim02improving.pdf" rel="nofollow noreferrer">Buchheim et al.</a>, improving Walker's algorithm to run in linear time.</p>

<p>Please do let me know should there be any need to improve my question, and thanks a lot in advance for any pointers.</p>

<p><strong>EDIT:</strong></p>

<p>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 <a href="http://eclipse.org/gef/" rel="nofollow noreferrer">Eclipse GEF</a> 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.</p>

CC BY-SA 3.0
2012-06-28T10:14:47.967Z
Do you need an algorithm or an existing tool? Graphviz (http://www.graphviz.org/) can do this. You specify the graph, possibly some formatting options (for different kinds of nodes and edges) and the tool will output a reasonably rendered graph.
Dave Clarke
CC BY-SA 3.0
2012-06-28T10:22:31.520Z
@DaveClarke: Thanks. I'm aware of Graphviz being able to do this. Unfortunately it doesn't seem that there's currently no possibility out there to use Graphviz with an editor based on the [Eclipse Graphical Editing Framework](www.eclipse.org/gef). Hence I'm looking for an actual algorithm. Unless somebody knows how to plug/port Graphviz to GEF of course :).
s.d
CC BY-SA 3.0
2012-06-28T16:15:46.607Z
It sounds like the OP is looking for an algorithm (or a problem formulation that captures the specification)
Suresh Venkat
CC BY-SA 3.0
2012-06-28T16:19:27.640Z
@SureshVenkat: Yes, thanks for clarifying.
s.d
CC BY-SA 3.0
2012-06-28T16:23:09.640Z
Do non-hierarchical edges go between (nodes, tokens), or are they limited to tokens only ?
Suresh Venkat
CC BY-SA 3.0
2012-06-28T16:55:44.127Z
@SureshVenkat They can go between (nodes, tokens), (tokens, tokens) and (nodes, nodes).
s.d
CC BY-SA 3.0
2012-06-29T07:01:24.620Z
@s.d: although your description is detailed, perhaps a picture of a real representative graph can help to answer your question. P.S. did you try a [survey on the subject](http://www.graphdrawing.org/literature/gdbiblio.pdf)?
Marzio De Biasi
CC BY-SA 3.0
2012-07-07T17:35:39.997Z
Q has no mention of editing & but in comment you turn down graphviz & seem to indicate you want to edit it with GEF. GEF is a general visual editing framework/API on which other "plugins" can build on. you seem to want a default graph layout by an algorithm which you can then revise. suggest you edit your question to reflect that. by the way believe graphviz can be used to generate coordinates which can then feed into a graph editor. re GEF graph editing see eg [professional graph layout for GEF](http://www.eclipsecon.org/2008/sub/attachments/Professional_Quality_Graph_Layout_for_GEF.pdf)
vzn
CC BY-SA 3.0
2012-07-18T14:37:32.343Z
@vzn: Thanks. I'd had a look at the reference you mention before, and it points towards proprietary software, which I cannot use. I've edited my question following your suggestion.
s.d
CC BY-SA 3.0
2012-08-17T16:37:53.907Z
??? all the tools cited are not proprietary afaik
vzn
<ds.algorithms><graph-algorithms><cg.comp-geom><graph-drawing>
Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?
s.d
# Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

(Asked by: username_0 on 2012-06-28)

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](https://cstheory.meta.stackexchange.com/questions/1541/are-graph-visualisation-algorithm-questions-in-the-scope-of-cstheory-stackexchan).

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.](http://dirk.jivausername_0e/papers/buchheim02improving.pdf), 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](http://eclipse.org/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.

**Tags:** ds.algorithms, graph-algorithms, cg.comp-geom, graph-drawing

> **Comments:**
> **username_1**: Do you need an algorithm or an existing tool? Graphviz (http://www.graphviz.org/) can do this. You specify the graph, possibly some formatting options (for different kinds of nodes and edges) and the tool will output a reasonably rendered graph.  
> **username_0**: @DaveClarke: Thanks. I'm aware of Graphviz being able to do this. Unfortunately it doesn't seem that there's currently no possibility out there to use Graphviz with an editor based on the [Eclipse Graphical Editing Framework](www.eclipse.org/gef). Hence I'm looking for an actual algorithm. Unless somebody knows how to plug/port Graphviz to GEF of course :).  
> **username_2**: It sounds like the OP is looking for an algorithm (or a problem formulation that captures the specification)  
> **username_0**: @SureshVenkat: Yes, thanks for clarifying.  
> **username_2**: Do non-hierarchical edges go between (nodes, tokens), or are they limited to tokens only ?  
> **username_0**: @SureshVenkat They can go between (nodes, tokens), (tokens, tokens) and (nodes, nodes).  
> **username_3**: @username_0: although your description is detailed, perhaps a picture of a real representative graph can help to answer your question. P.S. did you try a [survey on the subject](http://www.graphdrawing.org/literature/gdbiblio.pdf)?  
> **username_4**: Q has no mention of editing & but in comment you turn down graphviz & seem to indicate you want to edit it with GEF. GEF is a general visual editing framework/API on which other "plugins" can build on. you seem to want a default graph layout by an algorithm which you can then revise. suggest you edit your question to reflect that. by the way believe graphviz can be used to generate coordinates which can then feed into a graph editor. re GEF graph editing see eg [professional graph layout for GEF](http://www.eclipsecon.org/2008/sub/attachments/Professional_Quality_Graph_Layout_for_GEF.pdf)  
> **username_0**: @username_4: Thanks. I'd had a look at the reference you mention before, and it points towards proprietary software, which I cannot use. I've edited my question following your suggestion.  
> **username_4**: ??? all the tools cited are not proprietary afaik  

---

## 1 answers

### Answer by username_4 on 2012-07-18. Score: 1

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](https://mathoverflow.net/questions/15664/what-is-the-best-graph-editor-to-use-in-your-articles).

browsing the [graphviz gallery,](http://www.graphviz.org/Gallery.php) here are two graph types similar to what you want.

[ER diagram](http://www.graphviz.org/content/ER) and [traffic light](http://www.graphviz.org/content/traffic_lights).

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"](http://www.graphviz.org/pdf/dottyguide.pdf) by Koutsofious.

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


---

