\normalsize\rm
\chapter{Introduction}
\label{Chapter Introduction}

Visualization of structural information in form of graph layout diagrams
is getting increasing attention.
Graphs are widely used to model relational structures such as networks, 
e.g., of a subway, of computers or the internet. Applications arise 
in economics (project management, work-flow diagrams, 
entity-relationship diagrams), computer science (compiler and software 
development tools, data base modelling, algorithm animation), 
social science (social networks) and natural science (flow-diagrams in 
Chemistry, visualization of excavations in Archeology).

A graph drawing\index{graph drawing} algorithm takes as input a graph and computes
a layout\index{layout} of the graph, i.e., a drawing in two or three-dimensional 
space by assigning coordinates to the vertices and mapping each edge 
to a simple curve. In most cases,  these curves are straight lines 
or polygonal chains.

The layouts produced by a graph drawing algorithm should be ``aesthetically 
nice'' and ``easy-to-understand''. Some important criteria for readable
diagrams are a small number of edge crossings, evenly distributed vertices
and edges, short edges, few edge bends, a small layout area  or volume,
and a good angular resolution (see, e.g.,~\cite{Pur97}).

There is a wide variety of graph drawing methods that take
different aesthetic\index{aesthetic criteria} criteria into account. Drawing methods can
be classified according to the kind of drawings they produce (e.g.,
hierarchical drawings, orthogonal drawings, straight-line drawings, 
circular drawings), 
the model they use (e.g., force-directed, planarization), 
and the class of graphs they can be applied to (e.g., planar graphs, 
directed acyclic graphs, trees).

AGD, a library of {\bf A}lgorithms for {\bf G}raph {\bf D}rawing, 
offers a broad range of existing algorithms for 
two-dimensional graph drawing and tools for implementing new algorithms.

In our opinion the following design\index{design goals} goals are the most important
in the field of implementing graph drawing algorithms. We try
to address them in AGD as described in the following
sections.

\begin{description}

\item{\bf Flexibility}

  Since there are so many different approaches to graph drawing none
  of which can be ruled out a priori, it is important to provide the
  possibility of choosing among several different algorithms in order
  to get good results for a particular graph. Thus, systems offering
  only a single drawing algorithm are only of limited usefulness.

  A related issue is the visualization component. Since graph drawing
  often appears as a subtask in a complex application, it is necessary
  to offer the possibility of using an arbitrary visualization component.
  A system for drawing graphs which is tied to a specific form of
  visualization significantly reduces the range of possible applications.

\item{\bf Ease of Usage}

  If a system is hard to use, then only a minority of ``expert users''
  will be able to take advantage of it. Since we want to address a
  broad audience, we have to provide an easy interface.

\item{\bf Extensibility}

  Graph drawing is still a very active area of research. We want to
  help in closing the gap between interesting new ideas and usable
  software by providing a set of tools which helps in quickly and
  efficiently implementing new algorithms. In particular the reusage
  of already written modules appearing in the implementations of
  several graph drawing algorithms should be possible and easy.
  Moreover, some modules used by algorithms are exchangeable allowing
  to replace particular phases of an algorithm by new
  implementations.

\end{description}

{\large\bf New in Version \AGDVER}
 
\begin{description} \index{Version Macro}
\item[Version Macro] \verb|__AGD__|  (defined to 12 in this version)
  
\item[Integrated into LEDA] -- Only one installation procedure for both LEDA 
and AGD
 
\item[Layout Algorithms] -- InteractiveSugiyama: modified version of Sugiyama 
algorithm that allows to  add nodes and edges to a given Sugiyama layout  
 
\item[Planar Subgraphs] --  New Algorithm NaiveMaximalPlanarSubgraph for 
computing maximal planar subgraph of given non-planar graph  
 
\item[Crossing Minimization] --  New and improved variants of 
ShortestPathInserter 
\end{description}
Please read Changes.txt and Fixes.txt in the AGD\_docs directory for 
more information.
                                                

\section{Overview}

\subsection{The Structure of AGD}

The two main parts of AGD are a collection of
layout algorithms and a toolbox for 
extending the library by new implementations.

AGD is written in the programming language \CC{} and uses the LEDA\index{LEDA}
platform for combinatorial and geometric computing \cite{Mehlhorn-Naeher:CACM}.
The design of AGD is based on the object-oriented 
features of the \CC{}  programming language. In particular, each layout 
algorithm is implemented as a \CC{} class. There is a common base class
for all layout algorithms called \mbox{\tt LayoutModule}. The
main advantages of this approach are a generic interface to
all layout algorithms, which allows for an easy integration
into applications, and a mechanism for handling preconditions
and postconditions of algorithms in the base class which is simply
inherited by all algorithms.

\begin{figure}[ht]
\centerline{\epsfig{file=agd_overview.eps,width=.75\linewidth}}
\caption{A Sketch of the User's View of AGD}
\label{User's View}
\end{figure}

Figure~\ref{User's View} shows an overview of the AGD library
from the user's perspective. The class \mbox{\tt GridLayoutModule}
is a base class of the specific layout algorithms
\mbox{\tt Convex} or \mbox{\tt MixedModel}. \mbox{\tt GridLayoutModule}
provides operations for all layout algorithms which place the
vertices on integer coordinates.
Moreover, it defines a common
user interface for this type of layout algorithms.
\mbox{\tt GridLayoutModule} inherits from \mbox{\tt LayoutModule}
which provides common functionality and a basic interface for
all layout algorithms.

Depending on the application different types of visualization
of the computed layouts may be suitable including no visualization
at all (e.g., just using the computed vertex coordinates as input
to further computations). Thus it is important that the layout
algorithms are not tied to a specific visualization tool. In
AGD we achieve this goal by manipulating the graphical
attributes of a graph by means of a generic interface which is
defined in the abstract class \mbox{\tt LayoutInterface}. The user
can specify which package to use for representing and displaying
graphical attributes of a graph by choosing a predefined
specialization of \mbox{\tt LayoutInterface} (\mbox{\tt GraphWinInterface}
for LEDA's graph visualization component {\sc GraphWin} and
\mbox{\tt GraphletInterface} for the graph editor {\sc Graphlet}~\cite{H97}
are already available) or by deriving her own
class from \mbox{\tt LayoutInterface}.



\subsection{Layout Algorithms in AGD}

\index{layout algorithms}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\index{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 \cite{JT97}.

Currently, the following graph layout algorithms are available.

\begin{itemize}
  \item drawing planar graphs on the grid with straight edges

    {\tt FPPLayout} (de Fraysseix, Pach, and Pollack~\cite{dpp-hdpgg-90}),
    {\tt SchnyderLayout} (Schnyder~\cite{s-epgg-90}),
    {\tt Convex} (Kant~\cite{Kan96}),
    {\tt ConvexDraw} (Chrobak and Kant~\cite{ck-cgd3c-93}),
    {\tt Planar\-Straight} (Gutwenger and Mutzel~\cite{GM97}),
    {\tt PlanarDraw} (Gutwenger and Mutzel~\cite{GM97}),
    {\tt VisibilityRepresentation} (Rosenstiehl and Tarjan~\cite{rt-rplbo-86})

  \item drawing planar graphs on the grid with edge bends

    {\tt MixedModelLayout} (extension of Kant's algorithm~\cite{Kan96,GM98b}),
    {\tt Pure\-Orthogonal\-Layout} (Tamassia~\cite{t-eggmn-87}),
        {\tt QuasiOrthogonalLayout} and
        {\tt Orthogonal\-Layout} (extension of Tamassia's algorithm~\cite{t-eggmn-87,KM98})

  \item drawing special classes of planar graphs

    \mbox{\tt TreeLayout} (Reingold and Tilford, Walker~\cite{rt-tdt-81,w-npagt-90,Lei96})

  \item drawing general graphs

    \mbox{\tt PlanarizationLayout},
        \mbox{\tt PlanarizationGridLayout} (allow to use all planar graph drawing
        algorithms for drawing general graphs),
    \mbox{\tt SugiyamaLayout} (Sugiyama, Tagawa, and Toda~\cite{stt-mvuhs-81}),
    \mbox{\tt SpringLayout} (Fruchterman, Reingold~\cite{fr-gdfdp-91}),
    \mbox{\tt TutteLayout} (Tutte~\cite{t-hdg-63})

  \item drawing cluster-planar graphs

    \mbox{\tt ClusterOrthogonalLayout} (L\"utke H\"uttmann, Mutzel)

\end{itemize}



\subsection{Standard Interfaces}

\begin{figure}[t]
\centerline{\epsfig{file=std_int.eps,height=12cm}}
\caption{\label{Standard Interfaces}Standard Interfaces}
\end{figure}

Figure~\ref{Standard Interfaces} gives an overview of
the standard\index{standard interface} interface provided by layout algorithm modules.
Methods defined in base classes
are inherited by derived classes, e.g., the complete standard
interface of {\tt AGDModule} for retrieving general information
about a module is inherited by {\tt LayoutModule}.

The base classes {\tt AGD} and {\tt AGDModule} implement the handling of
preconditions and postconditions. Furthermore, {\tt AGDModule} defines
the standard interface to retrieve general information, e.g,
the name or the author of the algorithm.

{\tt LayoutModule} is the base class for layout algorithms
and defines the interface to check the precondition of a
layout algorithm given a specific graph, and to call the layout
algorithm. There are special calls for passing a plane
graph (represented by a planar map). Each {\tt call()}
function does not change the input graph, i.e., the input is a
{\tt const} parameter.

{\tt GridLayoutModule} provides further support for layout
algorithms that place the vertices and edge bends on
an integer grid, i.e, the function {\tt call\_grid()}
computes the grid layout. There is also an extended interface
for passing a plane graph.

Figure~\ref{Module Overview} gives an overview of all modules contained in AGD.
Some modules allow to use other modules for particular subtasks.
The particular implementation used for this subtask can be exchanged
at run time. We call these optional parameters of a module {\em module options\/}\index{module options}.
The figure lists the module options for each module and shows
which type of module has to be used.



\begin{figure}[t!]
\centerline{\epsfig{file=agd_overview_final.eps,height=14.1cm,angle=90}}
\caption{Module Overview}
\label{Module Overview}
\end{figure}



\section{Implementation of AGD}

\subsection{The Generic Graphics Interface}\label{Generic Graphics Interface}

\index{layout interface}The layout of a graph is expressed by
graphical\index{graphical attributes} attributes of
vertices and edges. Most graph drawing packages define an extended
graph data structure, and use this structure with their graph
drawing functions.

This approach contains several disadvantages: Many applications
that require graph layout algorithms have already defined
their own data structures, e.g., the graph editor {\sc Graphlet}
uses the class {\tt GT\_Graph} to represent a graph together
with its graphical attributes. Another disadvantage is that
a specific application could need further graphical attributes,
such as bitmaps or PostScript graphics, or the provided graph class
contains many unnecessary attributes.

AGD does not define an extended graph data structure,
but uses a generic interface class to access graphical attributes
in existing data structures. This makes it possible to use different
data structures representing layouts by implementing a specific
layout interface.

In a drawing of a graph, vertices are represented by graphical objects 
such as rectangles or circles usually containing a text label,
and edges are represented by curves (polylines or splines).
A layout algorithm does not need to know the specific details of
the graphical representation of a vertex, it is sufficient to know
its size. The algorithm computes a position for each vertex, 
and a list of bends for each edge. 
Some algorithms, e.g., visibility representation, in addition have to 
change the size of a vertex and to specify 
where exactly the edges are connected to the corresponding source 
and target vertices. These points of connection are often called 
{\em edge anchors}.

For the representation of edge\index{edge anchors} anchors we adopted the method
used in the {\sc Graphlet} system \cite{H97}. Each anchor $p$ is 
defined by a point with two
coordinates describing the relative position of $p$ with
respect to the position of the corresponding vertex $v$. The point $(0,0)$
corresponds to the center of $v$. The coordinates in the range
of $[-1\dots1]\times[-1\ldots1]$ are linearly mapped to the
bounding box of $v$ which is specified by the width and height of $v$.

The class {\tt LayoutInterface} defines a generic interface to
read and manipulate these basic attributes.
It does not store them, but
defines how these attributes are accessed. An implementation of
a layout interface is a class derived from {\tt LayoutInterface} that
implements the virtual methods for a specific data structure representing
a layout.

Furthermore, the class {\tt LayoutInterface} contains two notification methods.
The method {\tt update()} is called, when intermediate changes in the layout
shall be made visible, and the method {\tt refresh()} is called in order
to indicate that the topology of the associated graph has changed, e.g.,
nodes or edges have been inserted or deleted.

There are already several predefined specializations of
{\tt LayoutInterface} available in AGD: {\tt GraphWinInterface} and
{\tt GraphWinAnimInterface} for LEDA's graph visualization component
{\sc GraphWin}~\cite{LEDA-Manual}, {\tt PSInterface} for the output to
a {\sc PostScipt} file and {\tt AGDLayout} as a simple storage for
graphical attributes.
For an example of how to use a layout interface with a graph drawing
algorithm see Section~\ref{usage}.



\subsection{Handling Preconditions and Postconditions of Modules}
\label{precond}

\index{pre- and postconditions}There is no generic algorithm for drawing all types of
graphs, but a wealth of algorithms for different restricted
classes of input graphs (e.g., the input graph has to be planar,
simple and biconnected). Thus there is a natural need for
handling the precondition on the input graph of a particular
algorithm. A simple approach to this task is to describe the
precondition in the written documentation of the algorithm, and
to simply assume that the algorithm gets only valid input graphs.
However, this is quite unsatisfactory.

A related problem lies in coping with the different models of
drawing graphs, e.g., edges have bends or not, vertex coordinates are
integers or not. Again, a simple solution is to
describe the properties of the drawing in the documentation
and that is it. If in a particular application the user wants
to know, which of the available algorithms satisfy a certain
property, then there is no elegant way for the application to
answer the question.

Our solution to the problems described above is to provide a
mechanism for specifying, querying and checking the precondition
of an algorithm, and a mechanism for specifying and querying
properties of its output, which we call the postcondition of
the algorithm. These mechanisms are implemented in
the base classes {\tt AGD} and {\tt AGDModule} by means of hash
tables and they are easy to \mbox{(re--)use}.

Let us see an example. The precondition of a layout algorithm
is represented by a set
of properties of the input graph, and the postcondition by a set
of properties of the layout. They are usually
specified in the constructor of a particular algorithm class.
The following is the constructor of the class {\tt FPPLayout},
which implements the layout algorithm by de Fraysseix, Pach,
and Pollack~\cite{dpp-hdpgg-90}.

\vbox{\tt\small
\begin{verbatim}
FPPLayout::FPPLayout()
{
    add_precondition (key::planar);
    add_precondition (key::simple);
    add_precondition (key::no_self_loops);

    add_post_rule (key::straight_line);
    add_post_rule (key::no_crossings);
}
\end{verbatim}
}

In this case all input graphs have to be planar and simple
(no parallel edges are allowed) and they may not contain self
loops. The drawing that the algorithm produces for a valid input
graph is always planar (indicated by {\tt no\_crossings}) and the edges
are drawn as straight lines. Therefore, the precondition is $\{
\mbox{planar},\mbox{simple},\mbox{no self loops}\}$, and the
postcondition is $\{\mbox{straight-line},\mbox{no crossings}\}$.

The base class {\tt LayoutModule} defines a function {\tt check()} which gets
a potential input graph and checks whether it satisfies the
specified precondition. Function {\tt check()} simply uses the method
{\tt check\_graph()} of its base class {\tt AGDModule}, which is able
to check all common graph properties,
like, e.g., planarity, simplicity, biconnectivity. 
Moreover, there is the possibility to add new properties for
particular algorithms, and to extend the {\tt check\_graph()} method accordingly.
The {\tt check()} method is not called by default, if an algorithm
is executed, because there are possible situations where it does
not make sense to do so, e.g., an application can guarantee the
validity of the input because there is some preprocessing step
which only produces inputs satisfying all preconditions.





\section{Using AGD} \label{usage}

In the following, we present a complete example of extending the
library by a new layout algorithm. Moreover,
the {\tt main()} routine is an easy example of an application.
The algorithm added to the library simply assigns random coordinates
to the vertices for brevity.

{\small \tt
\begin{verbatim}
#include<AGD/LayoutModuleImpl.h>
#include<AGD/ConstLedaGraphConcept.h>
#include<AGD/GraphWinInterface.h>

class RandomLayout : public LayoutModuleImpl<ConstLedaGraphConcept>  
{
  public:
    RandomLayout();
    string name() const { return string("Random"); }
    string long_name() const { return string("Random Layout"); }
    string author() const { return string("NA"); }
    string impl_author() const { return string("David Alberts"); }
    string impl_date() const { return string("May 1997"); }
    AGDModule *clone() const { return new RandomLayout; }
  protected:
    void do_call(ConstLedaGraphConcept& C);
  private:
    random_source rs;
};

RandomLayout::RandomLayout()
{ add_post_rule (key::straight_line); }

void RandomLayout::do_call(ConstLedaGraphConcept &C)
{
  const graph &G = C.get_graph();
  LayoutInterface &A = C.get_layout();

  a.make_straight_line();  // remove all bend points

  node v;
  forall_nodes(v,G)
  {
    double x,y;
    rs >> x >> y;   // assigns pseudo-random numbers in the range [0..1]
    x *= 500.0;     // scale to [0..500]
    y *= 500.0;
    A.set_position(v,DPoint(x,y));
  }
}

int main()
{
  GraphWin GW;               // create a GraphWin                           (1)
  GW.open();                 // open it, and let user edit a graph          (2)
  graph& G = GW.get_graph(); // get the graph                               (3)
  GraphWinInterface GWI(GW); // create an interface to GW for AGD alg's     (4)
  RandomLayout RL;           // create an instance RL of RandomLayout       (5)
  RL.call(G,GWI);            // apply RL to G displaying it in GW           (6)
  GW.edit();                 // let the user edit the result                (7)
}
\end{verbatim}}

A new class {\tt RandomLayout} is created representing the new algorithm.
It is derived from the base class {\tt LayoutModuleImpl<ConstLedaGraphConcept>}.
The template argument {\tt ConstLedaGraphConcept} defines the implementation
concept used by {\tt RandomLayout}. In this case, the algorithm works
on a const LEDA graph, i.e., the implementation method {\tt do\_call()} does
not alter its input graph. There are also implementation concepts which allow
to manipulate the input graph by creating temporarily a copy (see
Chapter~\ref{Chapter Implementation of Layout Algorithms}). Apart from the
constructor, all methods in the class {\tt RandomLayout} are refinements
of virtual methods provided by its base class.

The constructor declares the precondition (none in this case) and
postcondition (all edges are straight lines) of the algorithm.
The refined public methods provide
information about the particular algorithm and implementation. The
protected method {\tt do\_call()} implements the drawing
procedure. It is called by the inherited public method {\tt call()}
(see {\tt main()}).

We describe the {\tt main()} function in more detail:
In line (1) we create an instance {\tt GW} of class {\tt GraphWin} as
visualization component. Line (2) displays {\tt GW} on the
screen and lets the user edit a graph. In line (3) we get a reference
to the graph which has been created. We create a layout interface
to {\tt GW} in line (4). We create an instance
of the {\tt RandomLayout} algorithm in line (5) and use it on {\tt G}
displaying the result again in {\tt GW} in line (6). Finally, we let the
user edit the resulting graph in line (7). The graph together with the
computed coordinates can be saved to disk, for example.

Before \texttt{call}ing an algorithm it is possible to check whether
a certain input graph satisfies the precondition of the algorithm
that should be applied using the {\tt check()} method. In our example
this is not necessary, since there are no restrictions on the input.
