From: ted.dunning@gmail.com   
      
   This sort of problem is known generically as graph layout problems.   
   There are many approximate algorithms for either minimum crossing or   
   best distance layouts, but deterministic answers are intractable (sorry   
   I can't give you the reference, but it is a well known result).   
   Deterministic answers for special kinds of graphs like trees can be   
   trivial but not necessarily.   
      
   In practice, if you are talking about presenting graphs to humans as   
   opposed to theoretically laying them out on paper, true minimum   
   crossing layouts are distinctly sub-par.  Minimum energy methods which   
   put virtual springs between all nodes with zero-energy length equal to   
   graph distance does a reasonably good job for some graphs.  The quick   
   lesson that you will learn is that few naturally occurring graphs are   
   suitable for direct presentation to humans on a 2-D display.  The first   
   node you hit with degree 1,000 will demonstrate this pretty quickly.   
   Even something as the link neighborhood around a web page is not   
   usually very amenable to this kind of display.  Much effort has gone   
   into building visualizations for real graphs with many results of   
   debatable utility.   
      
   Can you say more about what you are really after?   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)