Woodstock Blog

a tech blog for general algorithmic interview questions

[Google] Connect Graph Nodes and Avoid Intersect



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.


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.