Planar Graph Layouts

Question

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.

Do you want to know how to optimize graphviz's output or how to implement an edge overlap minimizer on your own? — Antti Huima, Feb 27 '10 at 16:27
I did some more research and for a graph of my size, multi-scale layout is the only option. So at the moment I'm looking at SFDP. A important SFDP attribute is level, which defines how many scales you want. — jameszhao00, Feb 27 '10 at 20:32

score 11 · Accepted Answer · edited Feb 27 '10 at 22:42

11

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.

edited Feb 27 '10 at 22:42

P Shved

96,026
17
121
165

answered Feb 27 '10 at 19:06

1

Link is broken. – Grim Sep 10 '16 at 05:52
3

If a graph is planar then you can generate an embedding with zero edge crossings (since that is the definition of a planar graph) - determining whether a graph is planar can be achieved in linear `O(N)` time [[1](https://archive.org/details/PlanarityTestingByPathAddition) [2](https://dl.acm.org/citation.cfm?id=321852)] and it is a small (and also `O(N)`) step to generate an embedding. For non-planar graphs then, yes, it is NP-hard to generate an embedding with minimal edge crossings but it cannot be a planar embedding/layout. – MT0 Oct 11 '17 at 22:12

score 5 · Answer 2 · edited Nov 08 '21 at 12:59

The following open source Java library has a couple of algorithms which may help in laying out planar graphs. https://github.com/trickl/trickl-graph

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

ChrobakPayneLayout (based on the Boost C++ implementation by Aaron Windsor) http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

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.

Planar Graph Layouts

2 Answers2

Linked