Experimental and Theoretical Results in Interactive Orthogonal Graph Drawing

Papakostas, Achilleas and Six, Janet M. and Tollis, Ioannis G. (1997) Experimental and Theoretical Results in Interactive Orthogonal Graph Drawing. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 371-386(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_61).

Full text not available from this repository.


Interactive Graph Drawing allows the user to dynamically interact with a drawing as the design progresses while preserving the user's mental map. This paper presents a theoretical analysis of Relative-Coordinates and an extensive experimental study comparing the performance of two interactive orthogonal graph drawing scenaria: No-Change, and Relative-Coordinates. Our theoretical analysis found that the Relative-Coordinates scenario builds a drawing that has no more than 3n-1 bends, while the area of the drawing is never larger than 2.25n². Also, no edge has more than 3 bends at any time during the drawing process. To conduct the expirements, we used a large set of test data consisting of 11,491 graphs (ranking from 6 to 100 nodes) and compared the behavior of the above two scenaria with respect to various aesthetic properties (e.g., area, bends, crossings, edge length, etc.) of the corresponding drawings. The Relative-Coordinates scenario was a winner over No-change under any aesthetic measure considered in our experiments. Moreover, the practical behavior of the two scenaria was considerably better than the established theoretical bounds, in most cases.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_61
Classifications: M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/110

Actions (login required)

View Item View Item