Universal Obstructions for Outerplanarity

Το κίνητρο αυτής της διπλωματικής εργασίας έγκειται στα πρόσφατα αποτελέσματα του Paul, του Πρωτόπαπα και του Θηλυκού, οι οποίοι πρότειναν ένα παραμετρικό πλαίσιο για τη μελέτη των γραφημάτων και των κλάσεων γραφημάτων. Η μελέτη των ελασσόνων γραφημάτων έχει οδηγήσει σε πολλά αλγοριθμικά και δομικά αποτελέσματα. Συχνά, όταν μελετάμε τη σχέση των ελάσσονων γραφημάτων, μας ενδιαφέρει το σύνολο των παρεμποδίσεων μία κλάσης γραφημάτων που είναι κλειστή ως προς ελάσσονα. Αν έχουμε μία τέτοια κλάση, τότε το σύνολο των παρεμποδίσεων ως προς ελάσσονα αυτής είναι το σύνολο των ελαχιστικών, ως προς τη σχέση του ελάσσονος, γραφημάτων που δεν ανήκουν στην κλάση. Είναι εύκολο να δει κανείς ότι ένα γράφημα ανήκει στην κλάση, αν και μόνο αν δεν περιέχει κανένα έλασσον που να είναι ισόμορφο με μία παρεμπόδιση της κλάσης. Το Θεώρημα των Robertson-Seymour συνεπάγεται ότι αυτό το σύνολο παρεμποδίσεων είναι πεπερασμένο (αν ταυτίσουμε ισόμορφα γραφήματα) για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα. Είναι, επιπλέον, γνωστό ότι το να ελέγξουμε αν ένα συγκεκριμένο γράφημα είναι ισόμορφο με κάποιο έλασσον ενός δοθέντος γραφήματος μπορεί να γίνει σε πολυωνυμικό χρόνο ως προς το μέγεθος του δεύτερου. Έτσι, το Θεώρημα των Robertson-Seymour συνεπάγεται ότι, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα, υπάρχει αλγόριθμος πολυωνυμικού χρόνου που ελέγχει αν η είσοδός του ανήκει σε εκείνη την κλάση. Ένα πρόβλημα με αυτή την προσέγγιση είναι ότι συχνά είναι δύσκολο να αναγνωριστούν ακριβώς οι παρεμποδίσεις μίας δοθείσας κλάσης. Όμως, οι κλάσεις για τις οποίες ενδιαφερόμαστε μπορούν συχνά να περιγραφούν ως κλάσεις όπου κάποια παράμετρος γραφημάτων είναι φραγμένη από μία συγκεκριμένη σταθερά. Αυτή η ιδέα βρίσκεται στα θεμέλια των πρόσφατων εργασιών του Paul, του Πρωτόπαπα και του Θηλυκού, όπου οι συγγραφείς ορίζουν ένα πλαίσιο που μας βοηθά να φράξουμε παραμέτρους ασυμπτωτικά. Υπό αυτό το πλαίσιο, ενδιαφερόμαστε πλέον για ακολουθίες γραφημάτων, τέτοιες ώστε μία δοθείσα παράμετρος να είναι μεγάλη σε ένα γράφημα, αν και μόνο αν το γράφημα περιέχει κάποιο έλασσον που να είναι ισόμορφο με κάποιο μεγάλο μέλος μίας από αυτές τις ακολουθίες. Ένα τέτοιο σύνολο ακολουθιών λέγεται καθολική παρεμπόδιση για την παράμετρο (και μπορούμε επίσης να αναφερθούμε και στις ίδιες τις ακολουθίες ως καθολικές παρεμποδίσεις για την παράμετρο), αν είναι πεπερασμένο και οι ακολουθίες είναι αύξουσες ως προς τη σχέση του ελάσσονος και δεν περιέχουν η μία την άλλη ασυμπτωτικά. Σε αυτή τη διπλωματική εργασία, μελετάμε την παράμετρο της εξωεπιπεδότητας και βρίσκουμε μία οικογένεια με επτά καθολικές παρεμποδίσεις για αυτή.

Authors dc:creator

• Λάρδας Εμμανουήλ
• Lardas Emmanouil

• Θετικές Επιστήμες
• Science

Language dc:language

English

Identifier

uoadl:5425499

OAI record oai:identifier

https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A5425499