Techniques for the Refinement of Orthogonal Graph Drawings

Current orthogonal graph drawing algorithms produce drawings which are generally good. However, many times the quality of orthogonal drawings can be signicantly improved with a postprocessing technique, called renement, which improves aesthetic qualities of a drawing such as area, bends, crossings, and total edge length. Renement is separate from layout and works by analyzing and then ne-tuning the existing drawing in an ecient manner. In this paper we dene the problem and goals of orthogonal drawing renement, review measures of a graph drawing’s quality, and introduce a methodology which eciently renes any orthogonal graph drawing. We have implemented our techniques in C++ and conducted experiments over a set of drawings from ve well known orthogonal drawing systems. Experimental analysis shows our techniques to produce an average 37% improvement in area, 23% in bends, 25% in crossings, and 37% in total edge length.