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