Flow Methods for Graph Drawing

Dorothea Wagner
Universit"at Konstanz

The construction of clear and readable drawings of graphs
is a basic problem arising in many fields of applications.
Well studied graph drawing models are straight-line drawings,
orthogonal drawings or layered drawings. Criteria for the readability
of drawings are e.g. the angle resolution in straight-line drawings
or the number of bends in orthogonal drawings.

In this talk, we discuss flow methods for the angle resolution in
straight-line drawings and for minimizing the number of bends in
orthogonal drawings. We concentrate on a result by Tamassia (1987)
saying that an orthogonal embedding with minimum number of bends
of a plane 4-graph can be constructed efficiently by solving a
minimum cost flow problem.

Furthermore, we address the dynamic graph drawing problem.
When given a dynamic graph, i.e. a graph that changes over the time,
one has to take into account not only static criteria as mentioned before,
but also the effort users spend to regain familiarity with the drawing.
We extend the flow methods for orthogonal drawings to dynamic graphs
in order to construct drawings satisfying a compromise of the static
and the dynamic optimization criteria again efficiently.