Mainly, two kinds of methods are employed to draw undirected graphs by us.
Force-Directed Algorithms
Force-directed methods define a force model (or an energy function) similar
to the system of springs or celestial bodies, and acquire the nice layout
by minimizing the function gradually.
An interesting video about force-based graph drawing algorithm:
Typically, the force-directed algorithms include Eades heuristic,Kamada-Kawai heuristic, Fruchterman-Reingold heuristic and Harel heuristic, etc.
The simplicity and flexibility of force-directed algorithms provide a solid
foundation to solve the general graph drawing problems. However, it requires
O(n^2) at least, and just is fit for the graphs with less than 50 vertices.
Spectral Graph Drawing
Spectral graph drawing computes the eigenvectors of the matrix associated
with graphs to acquire the nice layouts. Two typical matrices are often
adopted: adjacent matrix and Laplacian matrix. For instance, the energy
function dealing with the Laplacian matrix is shown:
The running speed of the spectral algorithms is extremely fast; however, the resulting drawings maybe too dense since there is no repulsive force preventing the vertices of the graphs from becoming too close.
Furthermore, we adopt the multi-level techniques to solve the problems on drawing large graphs. Some methods, such as quad-tree/oct-tree decomposition, constraint-normalization, are adopted to speed up the running speed. Please see my related papers for more details.