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

 
Το τεκμήριο παρέχεται από τον φορέα :
Πανεπιστήμιο Κρήτης
Αποθετήριο :
E-Locus Ιδρυματικό Καταθετήριο
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο




1994 (EL)
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


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.