Layout Algorithms in AGD

AGD contains classical graph drawing algorithms as well as implementations of new algorithms (in some cases extensions of the former). In particular, AGD is designed to support planar graph drawing algorithms and planarization methods in a flexible way. Moreover, AGD contains exact algorithms using ABACUS for NP-hard optimization problems occuring in graph drawing, e.g., crossing minimization, maximum planar subgraph. ABACUS is a software system providing a framework for the implementation of branch-and-cut algorithms [JT97].

Currently, the following graph layout algorithms are available.

• drawing planar graphs on the grid with straight edges

  FPPLayout (de Fraysseix, Pach, and Pollack [DPP90]), SchnyderLayout (Schnyder [Sch90]), Convex (Kant [Kan96]), ConvexDraw (Chrobak and Kant [CK93]), PlanarStraight (Gutwenger and Mutzel [GM97]), PlanarDraw (Gutwenger and Mutzel [GM97]), VisibilityRepresentation (Rosenstiehl and Tarjan [RT86])

• drawing planar graphs on the grid with edge bends

  MixedModelLayout (extension of Kant's algorithm [Kan96,GM98]), PureOrthogonalLayout (Tamassia [Tam87]), QuasiOrthogonalLayout and OrthogonalLayout (extension of Tamassia's algorithm [Tam87,KM98b])

• drawing special classes of planar graphs

  TreeLayout (Reingold and Tilford, Walker [RT81,Wal90,Lei96])

• drawing general graphs

  PlanarizationLayout, PlanarizationGridLayout (allow to use all planar graph drawing algorithms for drawing general graphs), SugiyamaLayout (Sugiyama, Tagawa, and Toda [STT81]), SpringLayout (Fruchterman, Reingold [FR91]), TutteLayout (Tutte [Tut63])

• drawing cluster-planar graphs

  ClusterOrthogonalLayout (Lütke Hüttmann, Mutzel)