Ένας Αλγόριθμος για το Σχεδιασμό Προσανατολισμένων Γράφων

 
This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share



1994 (EN)
An Algorithm to Layout Directed Graphs
Ένας Αλγόριθμος για το Σχεδιασμό Προσανατολισμένων Γράφων

Καραβασίλη, Μαρία (EL)
Karavassili, Maria (EN)

Μ. Κατεβαίνης

The use of images and diagrams is most of the times the most effective method for the transmission of abstract as well as concrete information, due to the inherent human ability to perceive more easily information displayed graphically. Graphs are a form of graphical representation of information. This thesis deals with the design and implementation of a graph layout algorithm for hierarchically drawn directed graphs. The algorithm is given as input the list of the edges of the graph and produces in the output the coordinates where each node should be put in order to produce an aesthetically pleasing drawing of the graph. A well known graph layout algorithm for directed graphs is the algorithm which was developed by Sygiyama, Tagawa and Toda (STT algorithm), and was a major concern for scientists during the past decade. We initially implemented this algorithm, which is time inefficient when drawing large graphs and it often creates unwanted edge bends. The new algorithm initially selects a spanning tree of the graph. Then, it traverses the spanning tree and rearranges its nodes in order to reduce the number of crossings between edges of the graph. In the end, it uses a tree layout algorithm which computes the coordinates of the nodes of the spanning tree. We present the algorithm we designed and evaluate it by comparing it with the STT algorithm. Our algorithm achieves layout times under 1 second for small and medium sized graphs and it can be as much as ten times faster that the STT algorithm for large graphs. Furthermore it minimizes the number of edge bends. (EN)

text

Πληροφοριακά Συστήματα και Τεχνολογία Λογισμικού

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

1997-06-2
1994-03-01




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)