Fastest Algorithm For Graph Planarization

Question

I'm using Processing to develop a navigation system for complex data and processes. As part of that I have gotten into graph layout pretty deeply. It's all fun and my opinions on layout algorithms are : force-directed is for sissies (just look at it scale...haha), eigenvector projection is cool, Sugiyama layers look good but fail fast on graphy graphs, and although I have relied on eigenvectors thus far, I need to minimize edge crossings to really get to the point of the data. I know, I know NP-complete etc.

I should add that I have some good success from applying xy boxing and using Sugiyama-like permutation to reduce edge crossings across rows and columns. Viz: graph (|V|=90,avg degree log|V|) can go from 11000 crossings -> 1500 (by boxed eigenvectors) -> 300 by alternating row and column permutations to reduce crossings.

But the local minima... whatever it is sticks around this mark, and the result is not as clear as it could be. My research into the lit suggests to me that I really want to use the planarization algorithm like what they do use for VLSI:

1. Use BFS or something to make the maximal planar subgraph 1.a. Layout the planar subgraph nice-like
2. Cleverly add outstanding edges to recover the original graph

Please reply with your thoughts on the fastest planarization algorithm, you are welcome to go into some depth about any specific optimizations you have had familiarity with.

Thanks so much!

Brick

Voting up because you came back and commented an answer after a year! :) – Otolith

Answer 1

Given that all graphs are not planar (which you know), it might be better to go for a "next-best" approach rather than a "always provides best answer" approach.

I say this because my roommate in grad school had the same problem you did. He was trying to convert a graph to planar form and all the algorithms that guarantee minimum edge crossings were too slow. What he ended up doing what just implementing a randomized algorithm. Basically, lay out the graph, then jigger nodes that have edges with lots of crossings, and eventually you'll handle the worst clumps of edges.

The advantages were: you can cut it out after a specific amount of time, so if you're time limited this always comes in under a certain amount of time, if you get a crappy graph you can just run it again (over the already laid out graph) to get something better, and it's relatively easy to code up.

Disadvantage is you don't always get the global minima in crossings, and if the graph gets stuck in high crossing areas, his algorithm would sometimes shoot a node way off into the distance to try and resolve it, which sometimes causes really weird looking graphs.

Dissipate

Okay that is obvious but I didn't think of it. Great idea. I will actually try that tomorrow. . . As well as attempting to implement Cai's planarization algorithm. – Brick

I know this is 1 year old, but that idea turned out to work surprisingly well. Sure it gets stuck after a while, but it worked pretty damn well...Maybe like simulated annealing. – Brick

It is very like simulated annealing. Glad it was useful! – Dissipate

I think you mean "not all graphs are planar" not "all graphs are not planar". – Ellon

Answer 2

You know already lots of graph layout but I believe your question is still, unfortunately, underspecified.

You can planarize any graph really quickly by doing the following: (1) randomly layout the graph on a plane (2) calculate where edges cross (3) create pseudo-vertices at the crossings (this is what you anyway do when you use planarity based layout for non-planar graphs) (4) the graph extended with the new vertices and split edges is automatically planar.

The first difficulty comes from having an algorithm that calculates a combinatorial embedding that minimizes the number of edge crossings. The second difficulty is using that combinatorial embedding to do layout in Euclidean plane that is visually appealing, e.g. for orthogonal graph layout you might want to minimize the number of bends, maximize the size of faces, minimize the area of the graph as a whole, etc., and these goals might conflict each other.

Summary

I'm not actually sure that your method is completely described...How do the dummy vertices help untangle the graph? What if I want to preserve the topology...and not add new edges? – Brick

When a graph is combinatorially non-planar you need to transform it to a planar one by turning edge crossings into extra vertices – Summary

@AnttiHuima I don't think it would be a real answer, the real problem remains exactly the same: how to minimize the crossings in the question, and how to minimize the pseudo-vertices in your answer. The only reason why I don't vote against your answer is that it can serve as a good starting point for thinking on a real one. – Wanton