Is there an algorithm for drawing planar graph if I have list of his faces?
I know there are some complex algorithms such as path addition and vertex addition, which test planarity and produce planar embedding but it's not what I'm looking for.
1
votes
1 Answers
1
votes
There are a host of techniques for visualizing graphs, with entire textbooks devoted to the subject. If you're looking for a quick algorithm to implement, I'd suggest looking at a force-directed graph drawing.
The idea is to consider vertices to naturally repel each other, but edges to draw them together. Both forces (repulsion and attraction) should be functions of distance between vertices, and act directly towards (or away from) the relevant vertex. Magnitudes like (1/r^2) for a repulsive force and ln(r) for an attractive force is good. Also consider some repulsive forces applied at boundaries to stop separate connected components flying off to infinity.
That algorithm goes something like:
Place all vertices at random points on the plane.
Calculate the net forces acting on each vertex.
Move each of the vertices by a fraction of the net forces.
If no vertex moved more than some tolerance value, draw the graph, else go to 2.
If you want an animation, you can replace step 4 with "draw the graph, then go to 2".
It's not quick, and it doesn't guarantee a planar representation, but it's straightforward to implement and generally does a good job of capturing planarity. Highly connected vertices end up close to each other.
