Χρωματισμοί, εμφυτεύσεις και συναφή γραφοθεωρητικά προβλήματα

Περίληψη

Οι εμφυτεύσεις γραφημάτων σε βιβλίο είναι ένα ευρέως μελετημένο κεφάλαιο τις θεωρίας γραφημάτων με πολλές εφαρμογές. Η σχετική ερευνητική δραστηριότητα χρονολογείται από τις αρχές της δεκαετίας του 70 και έχει παράξει πλούσια βιβλιογραφία. Στην παρούσα διδακτορική διατριβή εστιάζουμε σε δύο συγκεκριμένα προβλήματα. Το πρώτο τέθηκε από τον Heath: έδειξε ότι τα επίπεδα γραφήματα μέγιστου βαθμού 3 είναι υποχαμιλτονιανά και συνεπώς εμφυτεύονται σε βιβλίο με 2 σελίδες, και έθεσε το ερώτημα εάν το ίδιο ισχύει για επίπεδα γράφημα με μέγιστο βαθμό μεγαλύτερο του 3. Προς αυτή την κατεύθυνση, αποδεικνύουμε ότι όλα τα επίπεδα γραφήματα μέγιστου βαθμού 4 είναι πράγματι υποχαμιλτονιανά. Το δεύτερο πρόβλημα σχετίζεται με το πάχος εμφύτευσης σε βιβλίο γραφημάτων που δεν είναι κλειστά υπό ελάσσονα. Είναι γνωστό ότι εάν ένα γράφημα είναι κλειστό υπό ελάσσονα, τότε το πάχος εμφύτευσής του σε βιβλίο είναι φραγμένο. Ωστόσο, παρέμενε ανοιχτό εάν υπάρχει κάποιο φράγμα για οικογένειες γραφημάτων που δεν είνα ...
περισσότερα

Περίληψη σε άλλη γλώσσα

Book embeddings are a well studied topic of graph theory with numerous applications. Research dates back to early 70s and has produced a vast litterature. In this thesis we focus on two particular problems. The first was posed by Heath: he proved that planar graphs of maximum degree 3 are subhamiltonian and therofore 2-page book embeddable, and asked if the same holds for planar graphs of maximum degree greater than 3. In this concept we prove that all planar graphs of maximum degree 4 are indeed subhamiltonian. The second question is releted to the page number of graphs that are not closed under minors. It is well known that if a graph is closed under minors then its page number is bounded. However it remained open whether any bound exists for families of graphs that are not minor-closed. We prove that the class of 1-planar graphs, i.e. graphs that can be embedded in the plane so that every edge is crossed at most once, have bounded page number. To the best of our knowledge, this is t ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/43369
ND
43369
Εναλλακτικός τίτλος
Embeddings, colorings and related graph theoretic problems
Συγγραφέας
Ραυτοπούλου, Χρυσάνθη του Νικόλαος
Ημερομηνία
2016
Ίδρυμα
Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών
Εξεταστική επιτροπή
Παπαϊωάννου Αλέξανδρος
Συμβώνης Αντώνιος
Bollobas Bella
Kaufmann Michael
Εμίρης Ιωάννης
Αρβανιτάκης Αλέξανδρος
Φωτάκης Δημήτριος
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Λέξεις-κλειδιά
Θεωρία γραφημάτων; Απεικόνιση γραφημάτων
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
σχημ., γραφ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)