DFG Project: Neue Modelle und Methoden zum effektiven orthogonalen Layout von Graphen

In this project, we introduce and study new models and methods for effective orthogonal layout of graphs.

A smooth orthogonal drawing of a (planar) graph of maximum degree four is a (planar) drawing, in which each vertex occupies a point on the integer grid and has four available ports, and each edge is a sequence of axis- aligned segments and circular arc segments with common axis-aligned tangents (i.e., quarter, half or three-quarter arc segments).

Intuitively, in a smooth orthogonal drawing we replace the bends in orthogonal drawings by such circular segments while leaving the ports unchanged. Since the readability of orthogonal drawings decreases as the number of bends increases, replacing poly-line edges with smooth curves will result in drawings with improved readability and/or more aesthetic appeal.

A slanted orthogonal drawing of a (non-planar) graph of maximum degree four is a drawing in in which each vertex occupies a point on the integer grid and has four available ports, each edge is drawn as a sequence of horizontal, vertical and diagonal segments, such that a diagonal segment is never incident to a vertex, crossings always involve diagonal segments, and the minimum of the angles formed by two consecutive segments of any edge always is 135 degrees.

In the Slog model, we replace each normal orthogonal bend by two half-bends where each horizontal or vertical segment is followed by a diagonal segment using an angle of 135 degrees. The ports stay the same as before, the great advantage is that we can require that the crossings are only at diagonal segments which makes them clearly visible.