| Περίληψη |
Tο χαρακτηριστικό της οπτικοποίησης πληροφορίας (information visualization), και ειδικότερα η σχεδίαση γράφων, αποτελεί μια κρίσιμης σημασίας λειτουργικότητα για τις σύγχρονες εφαρμογές. Η ανάγκη της αυτόματης σχεδίασης γράφων ανακύπτει σε ποικίλες περιοχές, όπως η τεχνολογία λογισμικού, τα πληροφοριακά συστήματα και οι βάσεις δεδομένων. Στην παρούσα εργασία εισάγουμε μια καινούρια κλάση γράφων, τους οποίους ονομάζουμε χωροταξικούς γράφους. Σε έναν χωροταξικό γράφο υπάρχουν ετικέτες της μορφής 'δεξιά', 'κάτω', 'αριστερά', ή 'επάνω' επί των ακμών του. Δεδομένου ενός χωροταξικού γράφου G διατυπώνουμε το πρόβλημα της Σχεδίασης Πλαισίων ως εξής: Να αποφασισθεί εάν οι κόμβοι του G μπορούν να σχεδιασθούν στο επίπεδο ως ορθογώνια πλαίσια, έτσι ώστε οποιαδήποτε δύο πλαίσια των οποίων οι αντίστοιχοι κόμβοι ενώνονται με μια ακμή του G, να εφάπτονται σύμφωνα με την ετικέτα αυτής της ακμής. Το πρακτικό πρόβλημα που μοντελοποιούμε είναι το εξής: Έστω ότι διαχειριζόμαστε μια συλλογή D από αντικείμενα πληροφορίας (π.χ. μια βάση δεδομένων), κάθε ένα απ' τα οποία μπορεί να παρασταθεί οπτικά μέσα σε ένα ορθογώνιο πλαίσιο, όπως λ.χ. βλέπουμε στις διάφορες ιστοσελίδες. Τα αντικείμενα αυτά μπορεί να είναι τμήματα κειμένου, φωτογραφίες, σχήματα, λεζάντες, σύνδεσμοι σελίδων, γραμμές εργαλείων, διαφημιστικά πλαίσια, κ.ά. Ένα υποσύνολο αντικειμένων της μπορεί να επιλεγεί δυναμικά προς εμφάνιση, οπότε πρέπει να δημιουργηθεί μια σελίδα που θα διαμερίζεται σε ένα σύνολο πλαισίων, όπου σε κάθε ένα θα τοποθετηθεί ένα αντικείμενο. Για δύο αντικείμενα i1, i2 της συλλογής ενδέχεται να υπάρχει η συνθήκη ότι το i2 θα πρέπει να εμφανίζεται αμέσως προς τα δεξιά λ.χ. του i1, εκφράζοντας κάποια σχετική σημασία-σπουδαιότητα, οπότε τα αντίστοιχα πλαίσια θα πρέπει να εφάπτονται κατάλληλα. Στην εργασία μας μελετάμε τη δυνατότητα αυτόματης σχεδίασης μιας σελίδας που πρόκειται να εμφανισθεί στην οθόνη ενός υπολογιστή (π.χ. μια ιστοσελίδα). Μοντελοποιούμε κάθε αντικείμενο της συλλογής D με έναν κόμβο στο χωροταξικό μας γράφο G, και κάθε πληροφορία επαφής τους με μία ακμή στον G. Ορίζουμε το πρόβλημα της Σχεδίασης Πλαισίων και το επιλύουμε σε πολυωνυμικό χρόνο σε τρεις φάσεις, μέσω μιας γραμματικής χωρίς συμφραζόμενα, με εφαρμογή της θεωρίας επίπεδων γράφων και του γραμμικού προγραμματισμού. Η εργασία μας αποδεικνύει ότι η αυτόματη σελιδοποίηση (λ.χ. για εφαρμογές στον παγκόσμιο ιστό, ή/και για εφαρμογές που (επιχειρούν να) εξειδικεύουν την παρουσιαζόμενη πληροφορία με βάση ένα προφίλ χρήστη) είναι θεωρητικά εφικτή (γίνεται σε πολυωνυμικό χρόνο). Απομένει όμως να βελτιστοποιηθούν οι αλγόριθμοί μας ώστε να αποδίδουν σε συνθήκες "πραγματικoύ" χρόνο.
|
Αυτόματη Σχεδίαση Σελίδων : Μια Γραφοθεωρητική Προσέγγιση μλεσω Προσανατολίσιμων Κύκλων
