Your browser does not support JavaScript!

Αρχική    Dominance Drawing of Non-Planar Graphs  

Αποτελέσματα - Λεπτομέρειες

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 000375255
Τίτλος Dominance Drawing of Non-Planar Graphs
Άλλος τίτλος Κυριαρχική απεικόνιση μη-επίπεδων γράφων.
Συγγραφέας Κορναρόπουλος, Ευγένιος Εμμανουήλ
Σύμβουλος διατριβής Τόλλης, Ιωάννης
Περίληψη Η εκθετική αύξηση του όγκου δεδομένων στην εποχή μας χαρακτηρίζεται από σύνολα δεδομένων τόσο μεγάλα και περίπλοκα, που η επεξεργασία και η ανάλυσή τους είναι σχεδόν αδύνατη. Μια σειρά από δυσκολίες που παρουσιάζονται είναι η συλλογή, η αποθήκευση, η αναζήτηση, η ανάλυση και η απεικόνιση των δεδομένων. Σε αυτή την εργασία μελετάμε το τελευταίο απο τα παραπάνω προβλήματα, την απεικόνιση γράφων. Η χρήση απλών και διαισθητικών τεχνικών οπτικοποίησης κρίνεται πιο αναγκαία από ποτέ. Επεκτείνουμε την γνωστή τεχνική Κυριαρχικής Απεικόνισης (Dominance Drawing) χαλαρώνοντας ορισμένους περιορισμούς, έτσι ώστε να συμπεριλάβουμε την ευ- ρύτερη οικογένεια κατευθυνόμενων άκυκλων γράφων (DAG). Παρουσιάζουμε ένα νέο υπολογιστικό πρόβλημα το οποίο ορίζουμε ως Τοποθέτηση Υπό Ασθενή Κυριαρχία (Weak Dominance Placement), και αποδεικνύουμε την NPπληρότητά του χρησιμο- ποιώντας έννοιες από τον κλάδο της Θεωρίας Διάταξης. Αναφέρουμε ορισμένα φράγ- ματα και ιδιότητες αλλά και τρείς ευριστικούς αλγορίθμους για την εύρεση τοπικά βέλτιστων λύσεων. Χρησιμοποιώντας μια τοποθέτηση υπό ασθενή κυριαρχία, προτείνουμε μια νέα τε- χνική απεικόνισης κατευθυνόμενων άκυκλων γράφων που ονομάζεται Επικαλυπτόμενη Ορθογωνική Απεικόνιση (Overloaded Orthogonal Drawing). Για να απλοποιηθούν οι οπτικοποιήσεις χρησιμοποιούμε μια τεχνική υπερφόρτωσης για την δρομολόγηση των ακμών του γράφου. Οι προτεινόμενοι αλγόριθμοι είναι απλοί και εύκολα υλοποιήσιμοι σε κατευθυνόμενους άκυκλους γράφους ανεξάρτητα από το βαθμό των κόμβων, σε επίπεδους αλλά και σε μη-επίπεδους γράφους. Ακόμη παρουσιάζουμε φράγματα για τον αριθμό σημείων ανάκαμψης (bends) αλλά και για τον καταλαμβανόμενο χώρο της απεικόνισης. Η Επικαλυπτόμενη Ορθογωνική Απεκόνιση παρουσιάζει ορισμένα πολύ ενδιαφέροντα χαρακτηριστικά όπως την αποτελεσματική οπτική επιβεβαίωση ακμής, την απλότητα και την σαφήνεια οπτικοποιήσης. Επιπρόσθετα, εισάγουμε το πλαίσιο οπτικοποιήσης DAGView το οποίο μπορεί να απεικονίσει όχι μονο κατευθυνόμενους άκυκλους γράφους αλλά και γράφους με κύ- κλους, όπως και μη-κατευθυνόμενους γράφους. Η προσέγγισή μας συνδυάζει την αναγνωσιμότητα και την κλιμάκωση των μεθόδων απεικόνισης με πίνακα (matrix representation), με τη διαισθητικότητα που παρουσιάζουν οι γνωστές τεχνικές απει- κόνισης. Υλοποιήσαμε την μέθοδο οπτικοποίησης DAGView σε Java και τα αποτε- λέσματα είναι πολύ ενθαρρυντικά. Τέλος, πιστεύουμε ότι το πλαίσιο οπτικοποίησης DAGView θα είναι καλώς αποδεκτό σε Μελέτες Χρηστών, δεδομένου ότι οι οπτι- κοποιήσεις παρουσιάζουν αρκετά κριτήρια που προσδιορίζονται από τους ίδιους τους χρήστες ως σημαντικά οπως: η απεικόνιση σε υποκείμενο πλέγμα, τα κάθετα σημεία τομής, ο εύκολος έλεγχος για την ύπαρξη ακμής ή / και μονοπατιού, η διατήρηση του νοητικού χάρτη.
Φυσική περιγραφή xiv, 58 σ. : εικ., πίν. ; 30 εκ.
Γλώσσα Αγγλικά
Θέμα Dominance Drawings
Vizualization of Graphs
Απεικόνιση γράφων
Κυριαρχική απεικόνιση
Ημερομηνία έκδοσης 2012-07-20
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 153

Ψηφιακά τεκμήρια
No preview available

Προβολή Εγγράφου
Εμφανίσεις : 39