Drawing graphs using modular decomposition - Papadopoulos, Charis; Voglis, Costas (Journal of Graph Algorithms and Applications, 2007)
In this paper we present an algorithm for drawing an undirectedgraph G that takes advantage of the structure of the modulardecomposition tree of G. Specifically, our algorithm works bytraversing the modular decomposition tree of the input graph Gon n vertices and m edges in a bottom-up fashion until itreaches the root of the tree, while at the same time intermediatedrawings are computed. In order to achieve aesthetically pleasingresults, we use grid and circular placement techniques, andutilize an appropriate modification of a well-known springembedder algorithm. It turns out, that for some classes of graphs,our algorithm runs in O(n+m) time, while in general, the runningtime is bounded in terms of the processing time of the springembedder algorithm. The result is a drawing that reveals thestructure of the graph G and preserves certain aestheticcriteria. <!---->