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.
|Institution and School/Department of submitter:||Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών|
|Appears in Collections:||Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)|
Files in This Item:
|Papadopoulos-2007-Drawing graphs using.pdf||503.92 kB||Adobe PDF||View/Open Request a copy|
Please use this identifier to cite or link to this item:This item is a favorite for 0 people.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.