Drawing graphs with dotEmden R. Gansner and Eleftherios Koutsofios and Stephen NorthDecember 22, 2009Abstractdot draws directed graphs as hierarchies. It runs as a command line pro-gram, web visualization service, or with a compatible graphical interface.Its features include well-tuned layout algorithms for placing nodes and edgesplines, edge labels, “record” shapes with “ports” for drawing data struc-tures; cluster layouts; and an underlying file language for stream-orientedgraph tools. Below is a reduced module dependency graph of an SML-NJcompiler that took 0.23 seconds of user time on a 3 GHz Intel Xeon.1dot User’s Manual,December 22, 200921Basic Graph Draw ingdot draws directed graphs. It reads attributed graph text files and writes drawings,either as graph files or in a graphics format such as GIF, PNG, SVG, PDF, orPostScript.dot draws graphs in four main phases. Knowing this helps you to understandwhat kind of layouts dot makes and how you can control them. The layout proce-dure used by dot relies on the graph being acyclic. Thus, the first step is to breakany cycles which occur in the input graph by reversing the internal direction ofcertain cyclic edges. The next step assigns nodes to discrete ranks or levels. In atop-to-bottom drawing, ranks determine Y coordinates. Edges that span more thanone rank are broken into chains of “virtual”nodes and unit-length edges. The thirdstep orders nodes within ranks to avoid crossings. The fourth step sets X coordi-nates of nodes to keep edges short, and the final step routes edge splines. This isthe same general approach as most hierarchical graph drawing programs, based onthe work of Warfield [War77], Carpano [Car80] and Sugiyama [STT81]. We referthe ...
