How to reduce the number of crossing edges in a diagram?
Computing the absolute minimal crossing number is, as you observed, $\text{NP-hard}$. The process of drawing the graphs should be at least as hard as that.
The problem posed in the question is actually harder and more involved than the above. You are considering graph nodes of a certain size and shape while also bounding the size (area) of the result. In addition, a not yet determined notion of aesthetics is desired. Obviously we want a heuristic for this, which does not use the absolute minimum in the general case. The number of nodes encountered in such an application are likely not huge in the average case. Drawing the minimal edge crossing version of the graph may be feasible for small sizes.
Resources:
You may be interested in the following resources, particularly with the first:

The documentation for a feature of the Graphviz package presents an algorithm that generates nice looking directed graphs: http://www.graphviz.org/Documentation/TSE93.pdf
It has multiple other features that may prove useful. The source code is located on their website under EPL. It also includes a page dedicate to the theory behind graph visualization.
For a fixed-parameter algorithm check a paper by Martin Grohe:
Computing Crossing Numbers in Quadratic Time
A tech talk given by Amina Shabbeer at RPI:
Preserving Proximity Relations and Minimizing Edge-crossings in Graph Embeddings
An example of an efficient probabilistic algorithm can be found in this paper by Julia Chuzhoy:
An Algorithm for the Graph Crossing Number Problem

There are plenty of other resources, too. These should help you get started.
Additional Thoughts &amp; Observations:
Here is an idea to get around the issues concerning the shape and size of nodes. Given the graph (infinitely small nodes), expand each node while &quot;pushing&quot; or bending edges out of the way (ex. using splines while enforcing a limit on proximity). You need to do this with other edges and nodes that get in the way of it, which can start a chain reaction. Look into how an equilibriums can be efficiently computed (ex. molecular structures). If you cant get the shape of a node to the desired size, then scale the whole diagram.
A user might enjoy the results of a randomized algorithm. They could use your feature multiple times until they got something they liked. Avoid redundant computation in this case (no need to compute a crossing number again).