Call For Papers for Graph Drawing 2006, to be held next September in Karlsruhe, Germany. The submission deadline is June 4, a little over four three weeks away.


None: Non-planar graphs - how to print them on a plane?

Given an adjacency matrix, what's the best way of getting a plane representation (with 'bridges' if necessary - as few as possible and as nicely laid out as possible)?

Any ideas ?


11011110: Re: Non-planar graphs - how to print them on a plane?

Crossing minimization is hard in general, but there are a lot of heuristics known. Rather than try to explain it in the limited space for a comment here, I'd suggest consulting a graph drawing text — the one I'm using for my graph algorithms class this quarter is Graph Drawing by Di Battista, Eades, Tamassia, and Tollis, and some of the more relevant parts of it to this question are chapter 7 (incremental planarization) and chapter 9 (layered drawing).