Planar Graph Layouts

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 -

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


ANSWERS:


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:

Hope that helps.


The following open source Java library has a couple of algorithms which may help in laying out planar graphs.

In particular, the following classes provide analytic solutions to the problem:

ChrobakPayneLayout (based on the Boost C++ implementation by Aaron Windsor)

FoldFreeLayout (based on Anchor-Free Distributed Localization in Sensor Networks * Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine, and Seth Teller)

What you might want to do is use something like this as the first "attempt" which ensures no overlaps, although may not look great. Then you can apply a force-directed algorithm to space out the nodes more fairly.

Unfortunately, the library has only just been released so is short on documentation. It might however be useful by providing some actual code rather than just theory.



 MORE:


 ? Algorithm to draw connections between nodes without overlapping nodes
 ? How to implement a constraint solver for 2-D geometry?
 ? WPF Panel object placement logic: Is there an algorithm to distribute horizontally-fixed items vertically to prevent overlapping?
 ? Optimal flexible box layout algorithm
 ? Space filling with circles of unequal size
 ? Exploring an algorithm to find minimum chain containing certain items
 ? Given some AABBs, find minimum total surface area AABBs that contain them all?
 ? How to handle overlapping of dynamically placed labels
 ? Dynamically place nodes in cytoscape.js based on values, avoiding overlaps
 ? How to find list of possible words from a letter matrix [Boggle Solver]