******************************************************************
*                                                                *
*                   Algorithms and Options                       *
*                   ======================                       *
*                   AGD Server and AGD Demo                      *
*                                                                *
******************************************************************


In this file we briefly describe each algorithm provided 
by the AGD server, and give a short description of the 
available options. See file use_server.txt for detailed
information on using the AGD server and changing the default
options of the algorithms.

1. "de Fraysseix et al.":
-------------------------
a) Description:
This algorithm draws a planar graph G straight-line 
withouth crossings. G must not contain self-loops or 
multiple edges. The grid layout size is (2n-4)x(n-2)
for a graph with n nodes.

The algorithm runs in three phases. In the first phase, 
the graph is augmented by adding new artificial edges to
get a triangulated plane graph. Then a special order
(shelling) on the nodes of the graph is computed.
In the third phase the vertices are placed incrementally
according to the shelling order.

b) Options: None


2. "Schnyder":
--------------
a) Description:
This algorithm draws a planar graph G straight-line 
without crossings. G must not contain self-loops or 
multiple edges. The grid layout size is (n-2)x(n-2) 
for a graph with n nodes.

The algorithm runs in three phases. In the first phase, 
the graph is augmented by adding new artificial edges to 
get a triangulated plane graph. Then, a partition of the 
set of interior edges in three trees (also called 
Schnyder trees) with special orientation properties is 
derived. In the third step, the actual coordinates are 
computed.

b) Options: None


3. "Convex":
------------
a) Description:
This algorithm draws a planar, triconnected graph G 
straight-line without crossings. G must not contain 
self-loops or multiple edges. All faces are drawn 
convex, the grid layout size is at most (2n-4)x(n-2) 
for a graph with n nodes.

The algorithm runs in two phases. In the first phase,
a so-called shelling order for triconnected planar 
graphs is computed. Then, the vertices are placed 
incrementally according to the shelling order.

b) Options:
- size_opt: a boolean value determining if the grid 
  size of the layout is optimized compared to the 
  original Convex algorithm. This option reduces the 
  grid size especially for graphs with few edges.If 
  the graph is (almost) triangulated, the grid size 
  will be (almost) the same. (default: size_opt "true")

- base_ratio: a double value determining, how many 
  nodes are drawn on the base line 
  (default: base_ratio 0.33)
	

4. "ConvexDraw":
----------------
a) Description:
This algorithm draws a planar, triconnected graph G 
straight-line without crossings. G must not contain 
self-loops or multiple edges. All faces are drawn convex, 
the grid layout size is at most (n-1)x(n-1) for a graph 
with n nodes. 

The algorithm runs in two phases. In the first phase, a 
so-called shelling order for triangulated planar graphs is 
computed. Then, the vertices are placed incrementally 
according to the shelling order.

b) Options:
- size_opt: a boolean value determining if the grid 
  size of the layout is optimized compared to the 
  original ConvexDraw algorithm. This option reduces the 
  grid size especially for graphs with few edges.If 
  the graph is (almost) triangulated, the grid size 
  will be (almost) the same. (default: size_opt "true")
		
- tside_opt: a boolean value determining if it is allowed 
  to change the shape of the outerface (from a triangle) 
  in order to improve the grid size of the layout.
  (default: tside_opt "false")

- base_ratio: a double value determining, how many 
  nodes are drawn on the base line 
  (default: base_ratio 0.33)
		

5. "PlanarStraight":
--------------------
a) Description:
The algorithm is a generalization of the layout algorithm
Convex.

This algorithm draws a planar graph G straight-line
without crossings. G must not contain self-loops or 
multiple edges. The grid layout size is at most 
(2n-4)x(n-2) for a graph with n nodes.

The algorithm runs in three phases. In the first phase, 
the graph is augmented by adding new artificial edges to
get a biconnected plane graph (using a planar 
biconnectivity augmentation module). Then, a new shelling
order for biconnected planar graphs is computed. In the
third phase the vertices are placed incrementally according 
to the shelling order.

b) Options:
- size_opt: a boolean value determining if the grid 
  size of the layout is optimized compared to the 
  original Convex algorithm. This option reduces the 
  grid size especially for graphs with few edges.If 
  the graph is (almost) triangulated, the grid size 
  will be (almost) the same. (default: size_opt "true")
		
- max_outer: a boolean value determining if the algorithm 
  chooses the face of G with maximal degree as outerface 
  (|true|), or the first face in the list of faces.
  (default: max_outer "true")

- base_ratio: a double value determining, how many 
  nodes are drawn on the base line 
  (default: base_ratio 0.33)
		

6. "PlanarDraw":
----------------
a) Description: 
The layout algorithm PlanarDraw is a generalization of 
the algorithm ConvexDraw.

This algorithm draws a planar graph G straight-line 
without crossings. G must not contain self-loops or 
multiple edges. The grid layout size is at most 
(n-1)x(n-1) for a graph with n nodes.

The algorithm runs in three phases. In the first phase, 
the graph is augmented by adding new artificial edges 
to get a biconnected plane graph. Then, a new shelling 
order for biconnected planar graphs is computed. In the 
third phase the vertices are placed incrementally 
according to the shelling order.

b) Options:
- size_opt: a boolean value determining if the grid 
  size of the layout is optimized compared to the 
  original Convex algorithm. This option reduces the 
  grid size especially for graphs with few edges.If 
  the graph is (almost) triangulated, the grid size 
  will be (almost) the same. (default: size_opt "true")
		
- side_opt: a boolean value determining if it is 
  allowed to have slopes other than -1, 0, +1 on the 
  outerface. (default: side_opt "false")

- max_outer: a boolean value determining if the algorithm 
  chooses the face of G with maximal degree as outerface 
  (|true|), or the first face in the list of faces.
  (default: max_outer "true")

- base_ratio: a double value determining, how many 
  nodes are drawn on the base line 
  (default: base_ratio 0.33)

		
7. "Mixed-Model":
-----------------
a) Description:
The algorithm Mixed-Model is based upon the same ideas as 
Convex. In particular, the placement phase and the vertex 
boxes have been changed, and it has been generalized to 
work for connected planar graphs.

This algorithm draws a d-planar graph G on a grid such that 
every edge has at most three bends and the minimum angle 
between two edges is at least 2/d radians. G must not 
contain self-loops or mulitple edges. The grid size is at 
most (2n-6)x(3/2 n-7/2), the number of bends is at most 
5n-15, and every edge has length O(n) if G has n nodes.

The algorithm runs in several phases. In the preprocessing 
phase, vertices with degree one are temporarily deleted 
and the graph is augmented to a biconnected planar graph. 
Then, a shelling order for biconnected plane graphs is 
computed. In the next step, boxes around each vertex are 
defined in such a way that the incident edges appear 
regularly along the box. Finally, the coordinates of the 
vertex boxes are computed taking the degree-one vertices 
into account.

b) Options:
- base_ratio: a double value determining, how many 
  nodes are drawn on the base line 
  (default: base_ratio 0.33)

	
8. "PureOrthogonal":
--------------------
a) Description: 
This is a bend minimizing algorithm for the class of 
4--planar graphs. In addition to planarity, these graphs 
have the property that no vertex has more than four 
neighbours. Note that pure orthogonal drawings in which 
the vertices are mapped to points in the grid are only 
admissible for 4--graphs. For arbitrary planar graphs we 
provide two extensions of the orthogonal standard: They 
are realized by "QuasiOrthogonalLayout" and "OrthogonalLayout". 

The computation of the layout follows the so--called 
Topology--Shape--Metrics approach. The input is a 4--planar 
graph with fixed topology. According to this topology the 
algorithm constructs a network. A minimum--cost flow in 
this network determines a bend--minimal orthogonal 
representation for the input graph. In a last phase, a 
compaction assigns lengths to this representation and thus 
fixes the coordinates of the drawing.

b) Options:
- check: If this flag is set, the checking routines are 
  activated. Especially the orthogonal representation is 
  verified, certificating the correctness of the computation.
  (default: check "true")


9. "QuasiOrthogonalLayout":
---------------------------
a) Description:
The algorithm extends "PureOrthogonal" to planar graphs with
arbitrary degree.

The algorithm first transforms the graph to an auxiliary 
graph in which all the vertices have degree at most four. The 
idea is to internally represent all vertices with degree 
greater than four by an artificial region in which all 
adjacent vertices have degree three.  In the next phase, the 
bend minimization algorithm for planar 4-graphs is called 
(see "PureOrthogonal"), guaranteeing that each artificial 
region has rectangular shape. The last phase restores the 
original graph by applying the inverse of the first 
transformation. This guarantees that every node-induced 
subgraph containing vertices of degree at most four will be 
drawn bend-minimal and orthogonal. Hence, the algorithm 
generates drawings in the so-called quasi-orthogonal drawing 
standard.

b) Options:
- check: If this flag is set, the checking routines are 
  activated. Especially the orthogonal representation is 
  verified, certificating the correctness of the computation.
  (default: check "true")


10. "OrthogonalLayout":
-----------------------
a) Description:
The algorithm extends "PureOrthogonal" to planar graphs with 
arbitrary degree. It differs from "QuasiOrthogonalLayout" only 
in its output style. In an orthogonal drawing, vertices of 
degree greater than four are drawn as boxes whose corner points 
are mapped to grid points. The internal  computations are the 
same as in "QuasiOrthogonalLayout" and "PureOrthogonal".

b) Options:
- check: If this flag is set, the checking routines are 
  activated. Especially the orthogonal representation is 
  verified, certificating the correctness of the computation.
  (default: check "true")


11. "TreeLayout":
-----------------
a) Description:
This algorithm draws binary and general rooted trees. The 
graph G=(V,E) has to be directed, connected, and has to have 
exactly one source. Furthermore the equality |V|-1 = |E| must 
hold. 

The drawing is straight-line. Nodes of the same level are 
placed on a horizontal line. 

The algorithm works recursively starting on the lowest level 
of the tree. In each step, the subtrees of a tree vertex 
(that have been layed out already) are placed as closely to 
each other as possible. This guarantees to have small layout 
size. Moreover, isomorphic subtrees are layed out symmetrically.

b) Options:
- sib_separation: The spacing between two sibling nodes.
  (default: sib_separation 4.00)

- subtree_separation: The spacing between two adjacent subtrees.
  (default: subtree_separation 4.00)

- level_separation: The spacing between the nodes of two 
  adjacent levels. (default: level_separation 4.00)

- left_margin: Additional spacing at the left side of the drawing.
  (default: left_margin 0.00)

- upper_margin: Additional spacing at the top of the drawing. 
  (default: upper_margin 0.00)

	
12. "Sugiyama":
---------------
a) Description:
A general framework for drawing graphs with the hierarchical 
drawing method suggested by Sugiyama, Tagawa, and Toda. This 
method works in three phases:
1. Partition the nodes into levels using a RankAssignment module.
   Then, build a proper hierarchy, that is, reverse and split 
   edges until each edge is directed downwards and connects two 
   nodes on neighbored layers. The newly introduced nodes are 
   called "dummy nodes" and represent edge bends in the final 
   drawing.
2. Reorder the nodes on each layer in order to reduce the number
   of edge crossings. This is achieved by iteratively calling a 
   TwoLayerCrossMin module. The layers are alternately traversed 
   top--down and bottom-up, until the total number of crossings 
   does not decrease anymore.
3. Call a HierarchyLayoutModule to compute the final layout of 
   the hierarchy. This module assigns coordinates to nodes and 
   bend points to edges.

The above process can be repeated several times. Each repetition 
(except for the first) starts with a random order of the nodes on 
each layer. Since the total process of k-layer crossing 
minimization used here is a heuristic, each repetition may stop 
with a different total number of crossings. The algorithm chooses 
the result with the fewest number of crossings. If option transpose 
is set to true, a fine tuning step is performed after each 
traversal, which tries to reduce obvious crossings. In particular, 
the resulting ordering of the vertices on each layer is locally 
optimal with respect to transposition of adjacent vertices.

b) Options:
- ranking: The RankAssignment module used in the first phase of 
  the algorithm. (default: LongestPath, altenative DFS)

- heuristic: The TwoLayerCrossMin module used in the second
  phase of the algorithm. (default: Split, altenatives: Barycenter,
  Median, Greedy Insert, Greedy Switch)
		
- fixed_level_distance: a boolean value determining if the 
  distance between adjacent levels can vary.
  (default: fixed_level_distance "false")

- node_distance: a double value determining the distance 
  between two adjacent nodes on one layer.
  (default: node_distance 3.00)

- level_distance: a double value determining the minimum
  distance between two adjacent levels.
  (default: level_distance 3.00)


13. "Planarization":
--------------------
a) Description:
A general framework for drawing graphs with planarization. 
It applies a planarization module in order to transform a 
general graph into a planar graph by introducing dummy 
vertices at edge crossings, and draws the resulting planar 
graph using a layout algorithm for planar graphs. The 
planarization and planar layout algorithms are exchangeable 
modules allowing to use "Planarization" with different 
methods for planarization and planar drawing.

b) Options:
- layouter: The layout algorithm used for drawing the 
  planarized graph in "Planarization".
  (default: "QuasiOrthogonalLayout", alternatives:
   "de Fraysseix et al.", "Schnyder", "Convex", 
   "ConvexDraw", "PlanarStraight", "PlanarDraw",
   "Mixed-Model", "PureOrthogonal", "OrthogonalLayout")

		
14. "Spring Embedder":
----------------------
a) Description:
This algorithm draws a general graph G straight-line. 
The drawing of a planar graph can contain crossings.

The idea of the algorithm is the simulation of a system 
of mass particles. The vertices simulate mass points 
repelling each other and the edges simulate springs with 
attracting forces. The algorithm tries to minimize the 
energy of this physical system.

b) Options:
- noise: A boolean variable determining if the algorithm 
  performs random perturbations. (default: noise "true")

- iterations: An integer determining the number of main 
  steps that the algorithm performs. 
  (default: iterations 400)


15. "Tutte":
------------
a) Description:
This algorithm draws a planar graph G straight-line without 
crossings. It can also draw non-planar graphs.

The idea of the algorithm is to place every vertex into the
center of gravity by its neighbours. 

b) Options: None

		
16. "Visibility Representation":
--------------------------------
a) Description:
This algorithm draws a planar graph G such that each node is 
represented by a horizontal segment and each edge is 
represented by a vertical segment, and incidence between nodes 
and edges translates to intersection of horizontal and vertical 
segments. The grid size is at most (2n-4)x(n-1) for a graph 
with n nodes. G must not contain self-loops or multiple edges.

b) Options: None