I think position, grouping, order, and color can be used more effectively than they are used with hairballs.

In an ArcPlot, we can draw directed edges in one direction above the node plane, and edges in the other direction below the node plane. This becomes one effective use of positioning in a graph visualization.

In a CircosPlot, we use the circular positioning of nodes, but leverage ordering to convey meaning. Color can also be added in for subgrouping or for visualizing continuous values.

In a HivePlot, we use radial positioning of nodes to convey groupings/categories, and can use ordering within each groups. Links are then drawn between groups or within groups (within requires that the radial axis be cloned).