Graph drawing

The graph drawing (Engl. Graph Drawing ) is a topic of computer science and discrete mathematics that deals with graphs to realize geometrically. Algorithms that compute a two- dimensional embedding in Euclidean space for a given graph play a central role in graph drawing . The nodes of the graph are usually realized by simple geometric objects such as points , circles or squares . If there is an edge between two nodes, this is shown in the drawing by a Jordan curve which connects the objects assigned to the node.

Graph drawing is divided into two fields: In static graph drawing, a graph is to be displayed, while in dynamic graph drawing, entire sequences of graphs (usually in an animation ) are to be visualized.

approaches

In graph drawing, there are no universal techniques that can draw a graph. Depending on the area of application, different approaches are necessary which underline the respective effect to be achieved. The following explanations apply to both static and dynamic graph drawing.

Hierarchical drawing

Here one tries to read a hierarchy from a directed graph and then to represent it appropriately. For this purpose, the set of nodes is divided into equivalence classes so that nodes of an equivalence class are drawn at the same level. This creates a drawing that highlights the hierarchy prevailing in the graph.

In business process modeling , hierarchical graphs are used for value-added chain diagrams or organizational charts , among other things .

Alignment with the longest path

The combination determined between all start nodes (nodes without a predecessor) and end nodes (nodes without successors) in which the path between the start and end nodes has the largest number of nodes in between. This longest path then becomes the basis for the alignment of all nodes and edges, with the nodes and edges lying in the longest path being aligned with a straight line as far as possible and the nodes and edges not lying in the longest path being arranged around the straight line.

In business process modeling , graphs aligned with the longest path are used for EPCs , among other things . The use of auto-layout algorithms to calculate a graph that is aligned on the longest path is a problem with considerable development potential.

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

Force-based drawing

This approach is based on the model that forces act on all nodes . In this model, these forces result from the edges. Then you determine the total force that acts on each node and can thus get the positions of the nodes in the drawing. With this approach, edges are always represented by straight lines. In addition, more complex mathematical or pseudo-physical models can be used to calculate the forces. So z. B. all nodes repel each other (similar to an electrostatic force). Knots can also be simulated with different densities in a liquid medium , so that individual knots experience more or less buoyancy . In this way, drawings of the graph that appear more natural and can often be interpreted more intuitively are obtained.

Sketch-based drawing

In this case, a sketch of a graph is already available. An image for the graph is then generated from this. This method is used, for example, in cartography to simplify maps : Certain locations are filtered out of the map and streets between the selected locations are then represented by edges. In a drawing of this graph, all nodes are then drawn at the positions where they already appeared on the map. Edges then run mutually aligned (mostly as straight lines). The resulting image can be used, for example, as a route sketch or for bus timetables.

Types of drawings

Depending on the desired result, the type of drawings is divided into the following classes:

Orthogonal drawing

Orthogonal connection of nodes in a graph

In orthogonal drawings, edges are always shown as polygonal lines that are connected to one another at corners. All line segments run vertically or horizontally within the drawing , but never diagonally. Examples include a. Organizational charts .

Spline drawing

Spline connection of nodes in a graph

The edges are represented by curved lines that have no kinks. This can be achieved, for example, by using Bezier curves or B-spline curves .

For examples, see

Requirements for drawings

The representation of a graph should in no way appear confusing to a viewer, but should emphasize the special properties of the underlying graph. The selection of the algorithm for calculating the display is decisive. This algorithm should realize the most aesthetic representation of the graph. What is seen as the most aesthetic representation possible, however, depends on the one hand on the viewer's personal feelings and on the other hand on the intended purpose of the representation. However, there are measurable criteria by which the suitability of the representation for an intended purpose can be assessed, such as

the minimum distance and the minimum size of the nodes, influenced by the resolution of the displaying device,
the maximum distance and the maximum size of the nodes, influenced by the display area of the displaying device,
the variance of the edge lengths and node sizes (same size, graduated according to the golden ratio, any size),
the number of edge crossings,
the number of edge bends (for orthogonal edges) or edge support points (for spline edges),
the distance between neighboring nodes (as a measure of the free area between two nodes) or
Symmetries such as horizontal, vertical, diagonal, radial alignment or similar structures in partial graphs.

A special property of graphs is, for example, the presence of sources (nodes without incoming edges) or sinks (nodes without outgoing edges). This property is particularly emphasized by a hierarchical layout algorithm or a layout algorithm for alignment with the longest path .

In dynamic graph drawing, it is also important that successive graphs are not drawn too differently. For example, nodes that are retained from one graph to the next should, if possible, retain their position or at least their relative arrangements (horizontal and vertical node order). At this point it is assumed that a graph has a so-called mental map , which is usually perceived subconsciously by a viewer. The goal now is to get the mental map over the entire sequence. The influence of the mental map can depend on the way in which a dynamic graph is drawn. For example, it may be easier to make more changes in an animation than in a series of individual images in which one has to compare successive representations.

In addition to maintaining the mental map as a further requirement, the problem of drawing dynamic graphs can be further differentiated into two cases. This is because while a static graph must be completely available as input to an algorithm in order to be able to be drawn, it can be the case with a dynamic graph that only the next graph to be drawn is always available. One speaks in this case of interactive graph drawing or one in this online problem. In the offline case, the complete sequence of graphs is then available.

Applications

Graph drawing is used in the automatic arrangement of graph-based diagram types of various kinds, for example in business process modeling or software modeling . The auto-layout algorithms for creating the drawings can also be found in specialized commercial software libraries .

Software applications such as the diagram editor yEd offer extensive support for hierarchical, force and sketch-based drawing and enable both static and dynamic graph drawing.

Individual evidence

↑ Force-directed layout (in English) ( Memento of the original from June 21, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.

↑ Found in Space - 3-dimensional display for agile semantic networks ( page no longer available , search in web archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.@1@ 2Template: Dead Link / co-so.org
↑ Organigram ( Memento of the original from May 20, 2005 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
↑ aiSee.com graph database (in English) ( Memento of the original from March 13, 2009 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
↑ Unix Evolution ( Memento of the original from May 20, 2005 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
↑ aiSee.com Graph Database, Splines Examples (in English) ( Memento of the original from March 13, 2009 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
^ D. Archambault, H. Purchase, B. Pinaud: Animation, Small Multiples, and the Effect of Mental Map Preservation in Dynamic Graphs . In: IEEE Transactions on Visualization and Computer Graphics . tape 17 , no. 4 , April 1, 2011, ISSN 1077-2626 , p. 539-552 , doi : 10.1109 / TVCG.2010.78 ( ieee.org [accessed October 20, 2016]).
↑ Stephen C. North: Incremental layout in DynaDAG . In: Graph Drawing (= Lecture Notes in Computer Science ). No. 1027 . Springer Berlin Heidelberg, 1995, ISBN 978-3-540-60723-6 , pp. 409-418 , doi : 10.1007 / bfb0021824 ( springer.com [accessed October 20, 2016]).
↑ Diel, Stephan, Görg, Carsten, Kerren, Andreas: Preserving the Mental Map using Foresighted Layout . January 1, 2001, ISSN 1727-5296 , doi : 10.2312 / vissym / vissym01 / 175-184 ( eg.org [accessed October 20, 2016]).
↑ Beck, Fabian, Burch, Michael, Diehl, Stephan, Weiskopf, Daniel: The State of the Art in Visualizing Dynamic Graphs . January 1, 2014, doi : 10.2312 / eurovisstar.20141174 ( eg.org [accessed October 20, 2016]).
↑ Graph drawing software libraries ( Memento of the original from September 29, 2014 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2

Web links

[1] Force-directed layout (in English) ( Memento of the original from June 21, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2