 |
Constraint
Graph Layout for the Web
For applications which generate diagrammatic representations as
output automatic layout techniques are a crucial component. Automatic
presentation components are of particular importance in a web-based
setting, where the page designer cannot anticipate the exact viewing
conditions such as the size and aspect ratio of a particular display.
To optimise a presentation for the particular conditions encountered
at the time of retrieval, automated layout methods are indispensable.
Since graph-like network diagrams are among the most commonly used
types of diagrammatic displays, layout techniques for graphs have
been studied extensively and a number of different techniques have
emerged.
A well-established technique for automatic layout of graphs is based
on simulated annealing. While this is a comparatively versatile
technique that can take a variety of different esthetics and layout
objectives into account, it has its limits when a large number of
additional constraints are imposed on the optimal layout. Such constraints
arise in particular settings for example from requirements such
as aligned nodes, parallel of edges, particular groupings of nodes
etc.
We are investigating graph layout with a new extension of simulated
annealing, called "Constraint Simulated Annealing" that
can handle hard constraints such as above more effectively.
The results of this projects are published in
“Flexible Graph Layout for the Web”
by Trevor Hansen, Kim Marriott, Bernd Meyer and Peter Stuckey.
In Journal of Visual Languages and Computing, 13(1)2002:35-60.
Core Reference
“Drawing graphs nicely using simulated annealing” by
R. Davidson and D. Harel
in ACM Transactions on Graphics, 15(4):301-331, October 1996.
“Simulated annealing with asymptotic convergence for nonlinear
constrained global optimization” by
B.W. Wah and T. Wang.
In Proceedings of Principles and Practice of Constraint Programming,
pages 461-475. Springer-Verlag, 1999.
Student
Trevor Hansen
Supervisor
Bernd
Meyer
Type
Bachelor Computer Science (Honours)
Project Start
February 200
Project Completion
November 2000 |
|
|
Click
to print
