Tree graph drawing

Finally, I seem to be making some headway into graph drawing.  Over ten years ago, I had a similar problem.  In 1999, I worked for a company that sold a UML modeling tool, but I did not like the way it worked.  I tried to convince management that it needed changes to make it more useful,  but they brushed me off. So, I decided to try to write a UML modeling tool on my own.   Moreover, I wanted to expand my knowledge of computer science to include graph drawing, which is the field in computer science that tries to find two- or three-dimensional representations for graphs.   Unfortunately, I never succeeded in writing the tool at that time. I did not have enough time to learn graph  drawing because of a job change.  I spent several weeks trying to learn the subject,  but I was not able to grasp even the most basic algorithms.

Why was it hard to understand for me?  One problem was that I did not have access to the original papers on the subject. Instead, the only resource I had was  a textbook on the subject. In 1998, Prentice Hall published the only book on graph drawing that I could find (Di Battista, G., Eades, P., Tamassia, R. and Tollis, I.  Graph drawing: algorithms for the visualization of graphs. Prentice Hall PTR Upper Saddle River, NJ, USA, 1998).  Although it contains an excellent list of references, in itself it was unsuitable for learning graph drawing.  Unfortunately, most of the information in the book assumes prior knowledge of graph drawing and graph theory.   While I have had graduate-level classes in graph theory, I had no exposure to graph drawing.  I could not understand any of the algorithms in the book because the descriptions lacked sufficient detail in order  to translate them into an implementation.

But, I finally tracked down some of the original papers on the subject, and I now understand some hierarchy layout for rooted trees.  Several of the papers I have read include:

Bloesch, A. Aesthetic layout of generalized trees. Software—Practice & Experience, 23, 8 1993), 817-827.

Buchheim, C., Junger, M. and Leipert, S. Drawing rooted trees in linear time. SOFTWARE PRACTICE AND EXPERIENCE, 36, 6 2006), 651.

Reingold, E. and Tilford, J. Tidier Drawings of Trees. Transactions on Software Engineering1981), 223-228.

Walker II, J. A Node-positioning Algorithm for General Trees. Software – Practice and Experience, 20, 7 1990), 685-705.

I have a Silverlight implementation of these algorithms at http://domemtech.com/trees/index.html.

Leave a comment

Your email address will not be published.