<p>This question may not have been phrased to make it look research-level, but trying to compute the minimum number of crossings in a layout of a given graph is definitely a research-level problem.</p>

<p>One complication is that there is more than one definition of the number of crossings: see Pach, "Which crossing number is it, anyway?", FOCS 1998.</p>

<p>If you allow a drawing with curved edges, and count the number of intersection points of edges, then the problem is fixed-parameter tractable: it can be solved in time linear in the number of vertices in the graph, but exponential or worse in the number of crossings. See Kawarabayashi and Reed, "Computing crossing number in linear time", STOC 2007, as well as several previous related papers cited by them.</p>

<p>I don't think the Kawarabayashi-Reed algorithm is practical, but if you restrict attention to drawings with straight line segment edges (giving a different crossing number) there are more practical (though still exponential) approaches based on integer programming. See e.g. Jünger et al, "A polyhedral approach to the multi-layer crossing minimization problem", Graph Drawing 1997, and Buchheim et al, "A branch-and-cut approach to the crossingnumber problem", Discrete Optimization 2008.</p>

<p>If you want to test if there are no crossings at all (i.e. is the graph planar), then theoretically it has been known for decades that it can be solved in linear time, so this is no longer research-level. But finding a linear time algorithm that is also easy to implement and run in practice is not entirely a solved problem.</p>

CC BY-SA 3.0
2012-03-23T14:50:06.437Z
I think that Suresh’s criticism is not that graph drawing is not a research problem, but that the asker does not seem to have done homework on his/her part before asking the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-23T01:07:40.960Z
2012-03-23T01:07:40.960Z
David Eppstein
<p>I have an undirected graph on matris by vertex adjacency relations like that;</p>

<pre><code>/*    a  b  c  d
 * a -1  0  1  1
 * b  0 -1  1  1
 * c  1  1 -1  1
 * d  1  1  1 -1 
 *
 */
</code></pre>

<p>I want to draw this graph on cordinate system. What's the algorithm that gives each vertex position (x,y) by any method(force-directed, spring vs) with no intersection between edges or minimum intersection?
Thanks.</p>

CC BY-SA 3.0
2012-03-22T17:00:37.743Z
you are looking for a graph drawing algorithm. There are numerous papers on this, and a textbook, and a wikipedia page: http://en.wikipedia.org/wiki/Graph_drawing. Please refer to those, rather than posting a question that isn't research-level.
Suresh Venkat
CC BY-SA 3.0
2012-03-22T17:33:18.357Z
I didn't find any article about intersection between edges on graph drawing content. This is not research-level? Finding shortest way btw vertices is research content but non-intersection edges not?
moses
CC BY-SA 3.0
2012-03-22T19:05:40.777Z
graph drawing is all about drawing graphs with few or no intersections.
Suresh Venkat
<graph-theory><graph-algorithms><cg.comp-geom><graph-drawing>
Graph layout algorithm
moses
# Graph layout algorithm

(Asked by: username_0 on 2012-03-22)

I have an undirected graph on matris by vertex adjacency relations like that;
/*    a  b  c  d
 * a -1  0  1  1
 * b  0 -1  1  1
 * c  1  1 -1  1
 * d  1  1  1 -1 
 *
 */

I want to draw this graph on cordinate system. What's the algorithm that gives each vertex position (x,y) by any method(force-directed, spring vs) with no intersection between edges or minimum intersection?
Thanks.

**Tags:** graph-theory, graph-algorithms, cg.comp-geom, graph-drawing
> **Comments:**
> **username_1**: you are looking for a graph drawing algorithm. There are numerous papers on this, and a textbook, and a wikipedia page: http://en.wikipedia.org/wiki/Graph_drawing. Please refer to those, rather than posting a question that isn't research-level.  
> **username_0**: I didn't find any article about intersection between edges on graph drawing content. This is not research-level? Finding shortest way btw vertices is research content but non-intersection edges not?  
> **username_1**: graph drawing is all about drawing graphs with few or no intersections.  

---

## 1 answers

### Answer by username_2 on 2012-03-23. Score: 7

This question may not have been phrased to make it look research-level, but trying to compute the minimum number of crossings in a layout of a given graph is definitely a research-level problem.

One complication is that there is more than one definition of the number of crossings: see Pach, "Which crossing number is it, anyway?", FOCS 1998.

If you allow a drawing with curved edges, and count the number of intersection points of edges, then the problem is fixed-parameter tractable: it can be solved in time linear in the number of vertices in the graph, but exponential or worse in the number of crossings. See Kawarabayashi and Reed, "Computing crossing number in linear time", STOC 2007, as well as several previous related papers cited by them.

I don't think the Kawarabayashi-Reed algorithm is practical, but if you restrict attention to drawings with straight line segment edges (giving a different crossing number) there are more practical (though still exponential) approaches based on integer programming. See e.g. Jünger et al, "A polyhedral approach to the multi-layer crossing minimization problem", Graph Drawing 1997, and Buchheim et al, "A branch-and-cut approach to the crossingnumber problem", Discrete Optimization 2008.

If you want to test if there are no crossings at all (i.e. is the graph planar), then theoretically it has been known for decades that it can be solved in linear time, so this is no longer research-level. But finding a linear time algorithm that is also easy to implement and run in practice is not entirely a solved problem.

> **Comments:**
> **username_3**: I think that Suresh’s criticism is not that graph drawing is not a research problem, but that the asker does not seem to have done homework on his/her part before asking the question.  

---

