1
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ you are looking for a graph drawing algorithm. There are numerous papers on this, and a textbook, and a wikipedia page: en.wikipedia.org/wiki/Graph_drawing. Please refer to those, rather than posting a question that isn't research-level. $\endgroup$ – Suresh Venkat Mar 22 '12 at 17:00
  • $\begingroup$ 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? $\endgroup$ – moses Mar 22 '12 at 17:33
  • 7
    $\begingroup$ graph drawing is all about drawing graphs with few or no intersections. $\endgroup$ – Suresh Venkat Mar 22 '12 at 19:05
7
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 23 '12 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.