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

Abstract

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 the first attempt to bound the page number of such families of graphs. Another topic of graph theory that we focus on, are a variation of the well known total coloring problem. We consider total colorings that distinguish adjacent vertices by the sets of colors used for the vertex and its incident edges. This problem was proposed by Professor B\'ela Bollob\'as. In fact he suggested to consider AVD-total colorings of graphs with maximum degree 3, in order to answer a question posed by Hulgan of whether 5 colors suffice for such a coloring or 6 colors are necessary for certain 3-regular graphs. Although we did not manage to completely answer this question, we proved that 5 colors are enough for generalized Halin graphs with maximum degree 3. This is also a step towards determining the exact AVD-total coloring number of planar graphs. From another perspective, we also prove that the AVD-total coloring conjecture holds for 4-regular graphs. In this thesis, we also examine some problems of graph drawing. In particular, we answer an open question posed by Lov\'asz about circle representations of 4-regular planar graphs. Circle representations are related to the well known contact graph representation problem. We prove that if the graph is triconnected then circle-packing techniques can produce a realization as a system of touching circles, however if the graph is not triconnected then there exist infinite counterexamples. Also, we give new results on perfect smooth orthogonal layouts, that were recently introduced in the graph drawing litterature, and we extend and improve previous work on this topic.

Οι εμφυτεύσεις γραφημάτων σε βιβλίο είναι ένα ευρέως μελετημένο κεφάλαιο τις θεωρίας γραφημάτων με πολλές εφαρμογές. Η σχετική ερευνητική δραστηριότητα χρονολογείται από τις αρχές της δεκαετίας του 70 και έχει παράξει πλούσια βιβλιογραφία. Στην παρούσα διδακτορική διατριβή εστιάζουμε σε δύο συγκεκριμένα προβλήματα. Το πρώτο τέθηκε από τον Heath: έδειξε ότι τα επίπεδα γραφήματα μέγιστου βαθμού 3 είναι υποχαμιλτονιανά και συνεπώς εμφυτεύονται σε βιβλίο με 2 σελίδες, και έθεσε το ερώτημα εάν το ίδιο ισχύει για επίπεδα γράφημα με μέγιστο βαθμό μεγαλύτερο του 3. Προς αυτή την κατεύθυνση, αποδεικνύουμε ότι όλα τα επίπεδα γραφήματα μέγιστου βαθμού 4 είναι πράγματι υποχαμιλτονιανά. Το δεύτερο πρόβλημα σχετίζεται με το πάχος εμφύτευσης σε βιβλίο γραφημάτων που δεν είναι κλειστά υπό ελάσσονα. Είναι γνωστό ότι εάν ένα γράφημα είναι κλειστό υπό ελάσσονα, τότε το πάχος εμφύτευσής του σε βιβλίο είναι φραγμένο. Ωστόσο, παρέμενε ανοιχτό εάν υπάρχει κάποιο φράγμα για οικογένειες γραφημάτων που δεν είναι κλειστές υπό ελάσσονα. Αποδεικνύουμε ότι η οικογένεια των 1-επίπεδων γραφημάτων, δηλαδή των γραφημάτων που μπορούν να απεικονιστούν στο επίπεδο έτσι ώστε κάθε ακμή να τέμνεται το πολύ μία φορά, έχουν φραγμένο πάχος εμφύτευσης σε βιβλίο. Απ' όσο γνωρίζουμε, αυτή είναι η πρώτη απόπειρα προσδιορισμού κάποιου άνω φράγματος για το πάχος εμφύτευσης σε βιβλίο τέτοιων οικογενειών γραφημάτων. Ένα άλλο θέμα της θεωρίας γραφημάτων στο οποίο εστιάζουμε, είναι μία παραλλαγή του γνωστού προβλήματος ολικών χρωματισμών γραφημάτων. Εξετάζουμε ολικούς χρωματισμούς που διαχωρίζουν γειτονικές κορυφές βάση του συνόλου των χρωμάτων που χρησιμοποιούνται για την κορυφή και τις προσκείμενες ακμές της. Το πρόβλημα αυτό προτάθηκε από τον Καθηγητή B\'ela Bollob\'as. Βασικά πρότεινε να εξετάσουμε AVD-ολικούς χρωματισμούς γραφημάτων με μέγιστο βαθμό 3, προκειμένου να απαντηθεί ένα ερώτημα που τέθηκε από τον Hulgan και αφορά εάν 5 χρώματα επαρκούν για αυτόν το χρωματισμό ή απαιτούνται 6 χρώματα για ορισμένα 3-κανονικά γραφήματα. Αν και δεν καταφέραμε να απαντήσουμε συνολικά την ερώτηση αυτή, δείξαμε ότι 5 χρώματα επαρκούν για τα γενικευμένα Halin γραφήματα με μέγιστο βαθμό 3. Αυτό είναι επίσης ένα βήμα προς τον πλήρη προσδιορισμό του AVD-ολικού χρωματικού αριθμού των επίπεδων γραφημάτων. Από μία άλλη οπτική γωνία, δείξαμε επίσης ότι η εικασία των AVD-ολικών χρωματισμών ισχύει για 4-κανονικά γραφήματα. Στην παρούσα διδακτορική διατριβή, μελετήσαμε και ορισμένα προβλήματα της απεικόνισης γραφημάτων. Ειδικότερα, απαντάμε μία εικασία που διατυπώθηκε από τον Lov\'asz σχετικά με αναπαραστάσεις με κύκλους των 4-κανονικών επίπεδων γραφημάτων. Οι αναπαραστάσεις με κύκλους σχετίζονται με το γνωστό πρόβλημα αναπαράστασης γραφημάτων ως γραφήματα επαφών. Αποδεικνύουμε ότι εάν το γράφημα είναι τρισυνεκτικό, τότε τεχνικές συσκευασίας κύκλων μπορούν να χρησιμοποιηθούν για την κατασκευή μίας πραγματοποίησης ως ένα σύστημα εφαπτόμενων κύκλων. Ωστόσο, εάν το γράφημα δεν είναι τρισυνεκτικό υπάρχουν άπειρα αντιπαραδείγματα. Επίσης, παρουσιάζουμε καινούρια αποτελέσματα για άριστες ομαλές ορθογώνιες απεικονίσεις, οι οποίες εισήχθησαν πρόσφατα στην βιβλιογραφία της απεικόνισης γραφημάτων, και επεκτείνουμε και βελτιώνουμε προηγούμενα αποτελέσματα πάνω στο συγκεκριμένο πρόβλημα.