 | 
The research area of graph drawing has become an extensively
studied field which presents an exciting connection between
computational geometry and graph theory. The wide spectrum
of applications includes VLSIlayout, software engineering,
project management, database relations management, etc.
There are a lot of algorithms out there that take as input
a graph and try to produce a nice drawing of it. They use
different approaches and make nice drawings for the type of
graphs they are designed to draw best. For example tree
layouts produce very nice drawings of trees but if the
input graph is not a tree you will not be pleased by the
result.
There’s only one layout algorithm that can produce a nice
drawing of almost every kind of graph. This is the
Orthogonal Graph Layout Algorithm. As you can
expect its unmatched power and universality come with a
price – it is very complex and extremely hard to
implement. That’s why Nevron is proud to present you the
NOrthogonalGraphLayout class which implements the
orthogonal graph drawing algorithm.
An orthogonal drawing of a graph is an embedding in the
plane such that all edges are drawn as sequences of
horizontal and vertical segments. In particular for
nonplanar and nonbiconnected planar graphs, this is a big
improvement. The algorithm is complex and very hard to
implement, but it is fast and handles both planar and
nonplanar graphs at the same time.
Let G = (V; E) be a graph, n = |V|; m = |E|. A point
where the drawing of an edge changes its direction is
called a bend of this edge. If the drawing of an edge has
at most k bends we call this edge k-bent. An orthogonal
drawing is called an embedding in the rectangular grid if
all vertices and bendpoints are drawn on integer
coordinates.
Our algorithm takes as input a simple graph and produces
an orthogonal grid drawing. Note that if the input graph
is planar, the resulting drawing is also planar (i.e.
without edge crossings). In the case of non-planar graphs
the edge crossings are inevitable but the algorithm tries
to keep their number as low as possible. For both planar
and non-planar graphs the layout offers a great
improvement in the readability of the graph by maintaining
the following aesthetic criteria (given by their priority
in descending order):
- minimal number of edge crossings (0 for planar graphs)
- minimal number of bends
- minimal area of the final drawing
| |