Quick drawing of complex relationships

"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/