Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Thirteenth International Symposium on Graph Drawing, GD 2005
DOI: 10.7155/jgaa.00155
Drawing graphs using modular decomposition
Vol. 11, no. 2, pp. 481-511, 2007. Regular paper.
Abstract 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 aesthetically pleasing
results, we use grid and circular placement techniques, and
utilize an appropriate modification of a well-known spring
embedder algorithm. 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.
|
Journal Supporters
|