  Planar drawings of graphs tend to be favored over non-planar drawings.
Testing planarity and creating a planar layout of a planar graph can be done in
linear time. However, creating readable drawings of nearly planar graphs
remains a challenge. We therefore seek to answer which edges of nearly planar
graphs create clutter in their drawings generated by mainstream graph drawing
algorithms. We present a heuristic to identify problematic edges in nearly
planar graphs and adjust their weights in order to produce higher quality
layouts with spring-based drawing algorithms. Our experiments show that our
heuristic produces significantly higher quality drawings for augmented grid
graphs, augmented triangulations, and deep triangulations.
