views:

312

answers:

1

What are some edge overlap minimization techniques when laying out a graph? (Preferably related to GraphViz) Also are there any existing software that can layout a graph in a planar fashion?

Current Layout - http://www.evecakes.com/doodles/master.gif

The pink section in the upper left hand corner looks fine while the light blue section has some avoidable edge overlaps.

+2  A: 

For general graphs, the problem of a determining a planar layout of a graph with least edges crossing (the Crossing Number) is NP-hard. So some heuristic methods are used (like the Force based layout algorithms).

The page below briefly describes the graphviz algorithms and suggests some ways to use them for benefit. It also has links to the pdfs which should contain more information about the algorithms:

http://rss.acs.unt.edu/Rdoc/library/Rgraphviz/html/GraphvizLayouts.html

Hope that helps.

Moron
@Pavel: About the edit: according to paper _Crossing number is NP-complete". SIAM J. Alg. Discr. Meth._ finding crossing number is NP-Complete, but yes, the way I stated it, it looks like I am talking about actually finding the _layout_, and it is NP-Hard (easy reduction with crossing number), not sure about it being in NP.
Moron