Universität zu Köln

Hachul, Stefan and Jünger, Michael (2004). Drawing Large Graphs with a Potential -Field-Based Multilevel Algorithm. In: Graph drawing: 12th international symposium, GD 2004, New York, NY, USA, September 29 - October 2, 2004; revised selected papers, pp. 285-295. Springer.

Preview

PDF zaik2004-472.pdf Download (815kB) | Preview

Abstract

Force-directed graph drawing algorithms are widely used for drawing general graphs. However, these methods do not guarantee a sub-quadratic running time in general. We present a new force-directed method that is based on a combination of an efficient multilevel scheme and a strategy for approximating the repulsive forces in the system by rapidly evaluating potential fields. Given a graph G=(V,E), the asymptotic worst case running time of this method is {O}(|V|log|V|+|E|) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing 100000 nodes in less than 5 minutes. Furthermore, it clearly visualizes even the structures of those graphs that turned out to be challenging for some other methods.

Item Type:	Book Section
Creators:	Creators Email ORCID ORCID Put Code Hachul, Stefan UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548778
Title of Book:	Graph drawing: 12th international symposium, GD 2004, New York, NY, USA, September 29 - October 2, 2004; revised selected papers
Series Name:	Lecture Notes in Computer Science
Volume:	3383
Page Range:	pp. 285-295
Date:	2004
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54877