Planar graph drawing algorithm - Vertex placement

Question

Is there any simple algorithm for drawing a planar graph(if we have all vertices and edges needed). How to know the exact placements/positions of vertices?

Answer 1

The short answer is : it depends on what you want the graph to look like. The conceptually simplest graph layout algorithms are optimisation techniques like force-directed layout.

Roughly, you apply a kind of 'simulation' on the points of the graph, such that edges are modelled as springs and vertices clash if they get too close. An example of this is the Fruchterman-Reingold Algorithm.

Alternatively, you have to deal with the structure of the graph and layout the parts separately. Consider the simplest planar graph - a tree. For this, you find the center (either a single vertex or single edge) and layout the branches radially around this center. There are many tree layout algorithms known.

Now consider that many planar graphs can be described as a 'block-cut' tree where 2-connected components are the vertices of the tree, connected by cut edges. Each block (2-connected component) is laid out separately and then they are laid out according to the tree.

Going further, there are 3-connected planar graphs - such as the graphs of the Euclidian solids, and so on - that can be laid out with more complex algorithms and data strucutures like the SPQR tree.

So it really depends on how 'nice' you want the drawing to look, and how complex the input graph is.