[Google] Connect Graph Nodes and Avoid Intersect

Question

link

Draw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don’t intersect and they seem ordered.

Solution

There’s no clear solution. Someone suggest the following:

1. printing topological sort result (refer to post ‘Topology Sort’)
2. edges should not intersect, finding if a graph is planar

There’s various Planarity Testing Algorithms.