CODEWITHSUNDEEP
algorithmlayout
CJe
CJe

Reputation: 1992

Placing boxes in diagram the optimal way (no crossing lines)

I am doing an assignment where I have to draw a diagram on a web page with a number of boxes, some of which are to be connected by arrows. I have everything setup so that I'm able to draw the actual diagram, arrows and all but now I'm faced with the problem of placing the boxes in the optimal way. By this I mean laying out the page so that I have a minimum of lines crossing.

I have to do two types of diagrams: One is a more hierarchical diagram where I know which box to place top left and where all boxes form a hierarchy. The other is more tricky where no box needs to have a specific place and the end result is not a hierarchy. In either scenario are there more than one connection between two boxes. It's pretty much the same as laying out an E/R diagram for a database in the most readable way.

Does anyone know how to do this or where to find information about how to do this?

Thanks in advance

./CJ

Upvotes: 1

Views: 1177

Answers (1)

Rafe
Rafe

Reputation: 5295

Laying out an arbitrary graph with minimal crossings is an NP-hard problem, so you're left with finding a good heuristic.

What comes to mind is this:

  1. Lay your items on the perimeter of a circle with their connecting edges.
  2. Use simulated annealing to swap items, aiming to minimise the number of crossings.
  3. Tidy up using, say, force directed layout.

Another option would be to find a spanning tree, render that, then add in the back links. This may well produce more crossings than the simulated annealing approach, but it has the benefit of reusing the solution to the first part of your assignment.

Best of luck!

Upvotes: 2

Related Questions