Repository of UOI "Olympias"

Drawing graphs using modular decomposition (Journal article)

Papadopoulos, C./ Voglis, C.

In this paper we present an algorithm for drawing an undirected graph G that takes advantage of the structure of the modular decomposition tree of G. Specifically, our algorithm works by traversing the modular decomposition tree of the input graph G on n vertices and m edges in a bottom-up fashion until it reaches the root of the tree, while at the same time intermediate drawings are computed. In order to achieve aestheti- cally pleasing results, we use grid and circular placement techniques, and utilize an appropriate modification of a well-known spring embedder al- gorithm. It turns out, that for some classes of graphs, our algorithm runs in O(n+m) time, while in general, the running time is bounded in terms of the processing time of the spring embedder algorithm. The result is a drawing that reveals the structure of the graph G and preserves certain aesthetic criteria.