Home | deutsch  | Legals | Sitemap | Intranet | KIT
Portrait Monika Landgraf
Contact:
Monika Landgraf
Chief Press Officer, Head of Press Office

Phone: +49 721 608-47414
Fax: +49 721 608-43658
e-mail

Subscription of Press Releases

RSS-Feed

Press Release 109/2015

Quick Drawing of Complex Relationships

KIT Computer Scientists Publish “KaDraw“ Tool that Draws Complex Graphs 30 Times Faster than Tools Available so Far
2015_109_Schnelles_Zeichnen_von_komplexen_Beziehungen_72dpi
KaDraw draws complex graphs more efficiently and optimizes their representation. (Graphics: Dr. Christian Schulz, KIT)

Network plans of transportation companies, route planning for cars or dynamics of friendships in social networks: Man can capture detailed information best in a visual way. For a good readability of the corresponding graphs, computers have to calculate a good layout, i.e. optimum positions of all node points and connections. In case of a high level of detailing, an enormous computation capacity is required. To accelerate this drawing process, computer scientists of Karlsruhe Institute of Technology (KIT) have developed the “KaDraw” tool. It is now available for download under a general public license.

 

Quality criteria for a readable graphic representation of complex relationships are high. For example, the node points have to be located at sufficient distances in order to be identifiable. At the same time, the graph drawing tool has to arrange all edges in a way that they can be recognized by the viewer and do not overlap randomly. For this reason, all criteria to be observed are formulated in a target function. To optimize this function and to enhance the efficiency of computation, the team of Christian Schulz, Henning Meyerhenke, and Martin Nöllenburg of the KIT Institute of Theoretical Informatics developed the “KaDraw” tool for drawing graphs.

 

“KaDraw” is based on two methods. First, parallelization is achieved by using multi-core processors. This increases computation capacity, as the computation load is distributed to several processor cores. Second, innovative algorithms are applied. These algorithms generate a hierarchy of increasingly smaller graphs from the complex input graph. To obtain a good representation of the input graph, the smallest graph is drawn first. Then, the drawing is gradually transferred to larger graphs and improved on every larger level. “With this method, we can accelerate drawing by several factors. KaDraw can draw graphs about 30 times quicker than previous tools. And the quality of the results remains comparable,” Christian Schulz reports.

 

“KaDraw” cannot only draw static graphs quicker. Also dynamic graphs, i.e. graphs, the relationships of which change in the course of time, can be handled much more efficiently by the tool. An example of dynamic graphs are friendships in social networks. These are subject to constant change, as soon as additional friends are made. “In case of dynamic graphs, an already existing drawing can be input in the system. It then draws a new layout with new relationships,” Henning Meyerhenke explains.

 

Free Software

In a next step, the scientists plan to develop a method of increased efficiency. “By improving algorithmic complexity, we want to further enhance the efficiency of the method,” Martin Nöllenburg says. But before starting this work, “KaDraw” is made available to the public. From now on, the drawing tool will be available under a general public license (GPL). In parallel, the scientists will present their tool at the “Graph Drawing and Network Visualization” conference.

Link to download KaDraw: http://algo2.iti.kit.edu/kadraw/

 

 

Karlsruhe Institute of Technology (KIT) pools its three core tasks of research, higher education, and innovation in a mission. With about 9,300 employees and 25,000 students, KIT is one of the big institutions of research and higher education in natural sciences and engineering in Europe.

KIT – The Research University in the Helmholtz Association

ses, 24.09.2015

For further information, please contact:

Nils Ehrenberg
Pressereferent
Tel.: +49 721 608-48122
Fax: +49 721 608-43658
nils ehrenbergOkv7∂kit edu
The photo of printing quality may be requested by presseUna4∂kit edu or phone: +49 721 608-47414. The press release is available as a PDF file.