Bilkent University
Department of Computer Engineering


Improving the Compound Spring Embedder (CoSE) Algorithm for Speed and Quality


Hasan Balcı
PhD Student
Computer Engineering Department
Bilkent University

Compound Spring Embedder (CoSE) is an extended version of traditional force-directed layout scheme to support layout of compound graphs. Its ability to handle multi-level nesting, edges between nodes from different nesting levels and varying node sizes makes it one of the commonly used layout algorithms. The algorithm generally produces near-perfect end results; however, it behaves unexpectedly in some cases that lead to visually undesirable layouts. Moreover, because of its cubic (in the number of nodes) computational complexity, the algorithm performs poorly in terms of run time in large graphs. In this study, we aim to solve the unexpected behaviour of the algorithm by reconsidering the force model and improve the visual quality. In addition, we focus on decreasing the computational complexity of the algorithm to the quadratic level by enhancing the algorithm with Fruchterman and Reingold’s (FR) grid variant approach and the tree reduction method.


DATE: 16 October, 2017, Monday @ 15:40