I think you want to cluster them. Also, notice that in graphs that big, the biggest problem you will face is the big number of edges crossings which you don't want( and which you will probably not be able to avoid if a planar embedding does not exist ). If you do cluster them(on which criteria you decide) you will probably have less edge crossings inside the clusters so the drawing will be less confusing to the eye. Apart from that, you can look up force based algorithms, those can progressively find a planar embedding of the graph. Graphviz can use force-based algorithms if you use the fdp layout. Also see Visualizing very large datastructures thejit Graphing huge social networks.