Ένας Αλγόριθμος για το Σχεδιασμό Προσανατολισμένων Γράφων
Καραβασίλη, Μαρία
(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)
