| Algorithms based on force-directed placement and virtual physical models have become one of the most effective techniques for drawing undirected graphs. Spring-based algorithms that are the subject of this thesis are one type of force-directed algorithms. Spring algorithms are simple. They produce graphs with approximately uniform edge lengths, distribute nodes reasonably well, and preserve graph symmetries. A problem with these algorithms is that depending on their initial layout, it is possible that they find undesirable drawings associated with some local minimum criteria. In addition, it has always been a challenge to determine when a layout is stable in order to stop the algorithm.; In this thesis, we develop a simple but effective cost function that can determine a node layout quality as well as the quality of the entire graph layout during the execution of a Spring algorithm. We use this cost function for producing the initial layout of the algorithm, for helping nodes move out of unwanted local minima, and for providing robust stopping criteria. Furthermore, as a part of this thesis we develop LayoutShow: a signed applet/application for graph drawing and experimentation which includes the implementation of our Spring algorithm which we call CostSpring. |
