One of the best pieces of DAG layout software is available from Tom Sawyer
software. Their algorithm is based on Eli Messinger's Phd thesis at U.
Washington, 1988. They license a c++ and c library that does postscript.
Graph layout is NP-hard, but Messinger combined several approaches and added
some heuristics to improve on current work (at the time) to get a 5x
improvement. Tom Sawyer claims O() complexity.
contact: bmadden@tomsawyer.com
I am not aware of a share/free-ware version of this algorithm.
There are several LaTeX packages for drawing trees. You would need to write a
program (in such as Perl) to convert your description language to the tree
drawers'.
Details are in The Latex Companion by Goossens and all pp282,307 and the
relevant files can be downloaded from any CTAN archive - such as ftp.uk.ac.tex.
Search for tree.sty.
) complexity.