Graph algorithms

Hey /pros/, gimme graphing algorithms.  Specifically, I have a bunch of connected nodes.  The graph has a bunch of "input" nodes on the far left and a bunch of "output" nodes on the far right.  These are fixed and can't be repositioned.  In the middle is a rat's nest of connected nodes and anything goes (loops, self-connections, double connections, etc).  So, there's no guarantee that the graph can even be made planar (non-overlapping).  I need an algorithm that does the best possible job of moving those middle nodes around and sorting things out, efficiently.