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: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
URI: https://olympias.lib.uoi.gr/jspui/handle/123456789/12697
ISSN: 1526-1719
Publisher: Brown University
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Papadopoulos-2007-Drawing graphs using.pdf503.92 kBAdobe PDFView/Open    Request a copy


 Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12697
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.