Graph drawing

The graph drawing (English Graph Drawing ) is a topic of computer science and discrete mathematics, which is busy to realize geometric graphs. A central role in graph drawing form algorithms that compute a two -dimensional embedding in the Euclidean space for a given graph. The nodes of the graph are usually realized by simple geometric objects like points, circles, or squares. There is an edge between two nodes, this is indicated in the drawing by a Jordan curve that connects the node associated objects.

The graph drawing is divided into two fields: the static graph drawing a graph is to be displayed, while in the dynamic graph drawing whole sequences of graphs to be (usually in an animation ) visualized.

• 2.1 Orthogonal Drawing
• 2.2 Spline drawing

Approaches

In graph drawing there is no universal techniques that can draw a graph. Depending on the application, different approaches are needed that emphasize the respective effect to be achieved. The following explanations apply to both the static and for the dynamic graph drawing.

Hierarchical drawing

Here, one tries to read a hierarchy from a directed graph, and then appropriate fashion. For this purpose, the node-set is divided into equivalence classes so that nodes of an equivalence class are drawn on a height. The result is a drawing that highlights the dominant in the graph hierarchy.

In business process modeling hierarchical graphs are used inter alia for value chain diagrams or organization charts.

Orientation of the longest path

Here (nodes without predecessors ) is (nodes without successors ) is determined and end node that combination between all the start node at which the path between the start and end node therebetween lying nodes, the largest number. This longest path is then the basis for the alignment of all nodes and edges, which lie in the longest path nodes and edges are aligned as possible to a straight line which does not lie in the longest path nodes and edges are placed around the line around.

In business process modeling oriented graphs are used inter alia for EPCs longest path. The use of auto - layout algorithms to calculate an aligned longest path graph is a problem with significant development potential.

In software modeling, this representation can be used in the notation of BPMN and UML.

Forces based drawing

Underlying this approach is the model that affect all nodal forces. These forces arise in this model by the edges. Then, it determines the total force applied to each node, and may then obtain the position of the node in the drawing. Edges are always represented by straight lines with this approach. In addition, complex mathematical or pseudo- physical models for the calculation of forces can be applied. Thus, for example, can all nodes repel each other (similar to an electrostatic force ). Nodes can be simulated in a liquid medium with different density so that individual nodes to learn more or less lift. In this way, natural anmutendende and often intuitive interpretable drawings of graphs arise.

Sketch -based drawing

In this case, there is already a sketch of a graph. This then an image for the graph is generated. This method is used for example in simplifying application of maps: Certain places are filtered out of the map and then roads between the selected locations are represented by edges. In a drawing of this graph then all nodes are drawn at the positions where they already appeared on the map. Edges then run (mostly as straight lines ) are aligned with each other. The resulting image can be used for example as a map or for bus schedules.

Types of drawings

Depending on the desired result tells you the type of drawings in the following classes:

Orthogonal drawing

Edges are always represented in orthogonal drawings as polygons which are joined together at corners. All Linienzugsegmente here run vertically or horizontally, but never diagonally within the drawing. Examples include, without limitation Organizational charts.

Spline drawing

The edges are here represented by curved lines which have no kinks. This may be achieved for example through the use of Bezier curves or B- splines.

Examples, refer to

Requirements for Drawings

The representation of a graph should appear to a viewer confusing in any case, but should emphasize the special properties of the underlying graph. The choice of algorithm for computing the representation that is crucial. This algorithm is to realize an aesthetic portrayal of the graph. What is considered aesthetic representation possible, however, on the one hand by the personal feeling of the viewer and the other hand on the intended purpose of the representation dependent. There is still measurable criteria for the suitability of the representation may be evaluated for an intended purpose, such as

• The minimum distance and the minimum size of the nodes affected by the resolution of the performing unit,
• The maximum distance and the maximum size of the nodes affected by the display surface of the representative device,
• The variance of the edge lengths and node sizes (same size, graduated at the golden section, any size)
• The number of edge crossings,
• The number of the edge bends ( at orthogonal edges) or edge points ( in spline edges),
• The distance between adjacent nodes to each other ( as a measure of the free space between two nodes ), or
• Symmetries such as horizontal, vertical, diagonal, radial orientation, or similar structures in subgraphs.

A special feature of the graph, for example the presence of sources ( nodes without incoming edges) or sinks ( nodes without outgoing edges). This property is particularly highlighted by a hierarchical layout algorithm or a layout algorithm for aligning the longest path.

In a dynamic graph drawing is additionally important that successive graphs are not drawn to different. Nodes that are preserved example of a graph to the next, as possible should retain their position. At this point, it is assumed that a graph called a mental map has to be perceived by a viewer subconsciously. The goal now is to get the mental map on the entire sequence.

Applications

Graph drawing has application in the automatic set of graphs based on graph types of all kinds, such as business process modeling or the modeling software. The auto layout algorithms to create the drawings can also be found in specialized commercial software libraries.

Software applications such as the Graph Editor yEd offer extensive support for hierarchical, forces and sketch -based drawing and enable both static and dynamic graph drawing.