{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:5425499"},"canonical_url":"https://search.dev.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:5425499","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Universal Obstructions for Outerplanarity","abstract":"Το κίνητρο αυτής της διπλωματικής εργασίας έγκειται στα πρόσφατα αποτελέσματα του Paul, του Πρωτόπαπα και του Θηλυκού, οι οποίοι πρότειναν ένα παραμετρικό πλαίσιο για τη μελέτη των γραφημάτων και των κλάσεων γραφημάτων. Η μελέτη των ελασσόνων γραφημάτων έχει οδηγήσει σε πολλά αλγοριθμικά και δομικά αποτελέσματα. Συχνά, όταν μελετάμε τη σχέση των ελάσσονων γραφημάτων, μας ενδιαφέρει το σύνολο των παρεμποδίσεων μία κλάσης γραφημάτων που είναι κλειστή ως προς ελάσσονα. Αν έχουμε μία τέτοια κλάση, τότε το σύνολο των παρεμποδίσεων ως προς ελάσσονα αυτής είναι το σύνολο των ελαχιστικών, ως προς τη σχέση του ελάσσονος, γραφημάτων που δεν ανήκουν στην κλάση. Είναι εύκολο να δει κανείς ότι ένα γράφημα ανήκει στην κλάση, αν και μόνο αν δεν περιέχει κανένα έλασσον που να είναι ισόμορφο με μία παρεμπόδιση της κλάσης. Το Θεώρημα των Robertson-Seymour συνεπάγεται ότι αυτό το σύνολο παρεμποδίσεων είναι πεπερασμένο (αν ταυτίσουμε ισόμορφα γραφήματα) για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα. Είναι, επιπλέον, γνωστό ότι το να ελέγξουμε αν ένα συγκεκριμένο γράφημα είναι ισόμορφο με κάποιο έλασσον ενός δοθέντος γραφήματος μπορεί να γίνει σε πολυωνυμικό χρόνο ως προς το μέγεθος του δεύτερου. Έτσι, το Θεώρημα των Robertson-Seymour συνεπάγεται ότι, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα, υπάρχει αλγόριθμος πολυωνυμικού χρόνου που ελέγχει αν η είσοδός του ανήκει σε εκείνη την κλάση. Ένα πρόβλημα με αυτή την προσέγγιση είναι ότι συχνά είναι δύσκολο να αναγνωριστούν ακριβώς οι παρεμποδίσεις μίας δοθείσας κλάσης. Όμως, οι κλάσεις για τις οποίες ενδιαφερόμαστε μπορούν συχνά να περιγραφούν ως κλάσεις όπου κάποια παράμετρος γραφημάτων είναι φραγμένη από μία συγκεκριμένη σταθερά. Αυτή η ιδέα βρίσκεται στα θεμέλια των πρόσφατων εργασιών του Paul, του Πρωτόπαπα και του Θηλυκού, όπου οι συγγραφείς ορίζουν ένα πλαίσιο που μας βοηθά να φράξουμε παραμέτρους ασυμπτωτικά. Υπό αυτό το πλαίσιο, ενδιαφερόμαστε πλέον για ακολουθίες γραφημάτων, τέτοιες ώστε μία δοθείσα παράμετρος να είναι μεγάλη σε ένα γράφημα, αν και μόνο αν το γράφημα περιέχει κάποιο έλασσον που να είναι ισόμορφο με κάποιο μεγάλο μέλος μίας από αυτές τις ακολουθίες. Ένα τέτοιο σύνολο ακολουθιών λέγεται καθολική παρεμπόδιση για την παράμετρο (και μπορούμε επίσης να αναφερθούμε και στις ίδιες τις ακολουθίες ως καθολικές παρεμποδίσεις για την παράμετρο), αν είναι πεπερασμένο και οι ακολουθίες είναι αύξουσες ως προς τη σχέση του ελάσσονος και δεν περιέχουν η μία την άλλη ασυμπτωτικά. Σε αυτή τη διπλωματική εργασία, μελετάμε την παράμετρο της εξωεπιπεδότητας και βρίσκουμε μία οικογένεια με επτά καθολικές παρεμποδίσεις για αυτή.","abstract_html":"Το κίνητρο αυτής της διπλωματικής εργασίας έγκειται στα πρόσφατα αποτελέσματα του Paul, του Πρωτόπαπα και του Θηλυκού, οι οποίοι πρότειναν ένα παραμετρικό πλαίσιο για τη μελέτη των γραφημάτων και των κλάσεων γραφημάτων. Η μελέτη των ελασσόνων γραφημάτων έχει οδηγήσει σε πολλά αλγοριθμικά και δομικά αποτελέσματα. Συχνά, όταν μελετάμε τη σχέση των ελάσσονων γραφημάτων, μας ενδιαφέρει το σύνολο των παρεμποδίσεων μία κλάσης γραφημάτων που είναι κλειστή ως προς ελάσσονα. Αν έχουμε μία τέτοια κλάση, τότε το σύνολο των παρεμποδίσεων ως προς ελάσσονα αυτής είναι το σύνολο των ελαχιστικών, ως προς τη σχέση του ελάσσονος, γραφημάτων που δεν ανήκουν στην κλάση. Είναι εύκολο να δει κανείς ότι ένα γράφημα ανήκει στην κλάση, αν και μόνο αν δεν περιέχει κανένα έλασσον που να είναι ισόμορφο με μία παρεμπόδιση της κλάσης. Το Θεώρημα των Robertson-Seymour συνεπάγεται ότι αυτό το σύνολο παρεμποδίσεων είναι πεπερασμένο (αν ταυτίσουμε ισόμορφα γραφήματα) για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα. Είναι, επιπλέον, γνωστό ότι το να ελέγξουμε αν ένα συγκεκριμένο γράφημα είναι ισόμορφο με κάποιο έλασσον ενός δοθέντος γραφήματος μπορεί να γίνει σε πολυωνυμικό χρόνο ως προς το μέγεθος του δεύτερου. Έτσι, το Θεώρημα των Robertson-Seymour συνεπάγεται ότι, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα, υπάρχει αλγόριθμος πολυωνυμικού χρόνου που ελέγχει αν η είσοδός του ανήκει σε εκείνη την κλάση. Ένα πρόβλημα με αυτή την προσέγγιση είναι ότι συχνά είναι δύσκολο να αναγνωριστούν ακριβώς οι παρεμποδίσεις μίας δοθείσας κλάσης. Όμως, οι κλάσεις για τις οποίες ενδιαφερόμαστε μπορούν συχνά να περιγραφούν ως κλάσεις όπου κάποια παράμετρος γραφημάτων είναι φραγμένη από μία συγκεκριμένη σταθερά. Αυτή η ιδέα βρίσκεται στα θεμέλια των πρόσφατων εργασιών του Paul, του Πρωτόπαπα και του Θηλυκού, όπου οι συγγραφείς ορίζουν ένα πλαίσιο που μας βοηθά να φράξουμε παραμέτρους ασυμπτωτικά. Υπό αυτό το πλαίσιο, ενδιαφερόμαστε πλέον για ακολουθίες γραφημάτων, τέτοιες ώστε μία δοθείσα παράμετρος να είναι μεγάλη σε ένα γράφημα, αν και μόνο αν το γράφημα περιέχει κάποιο έλασσον που να είναι ισόμορφο με κάποιο μεγάλο μέλος μίας από αυτές τις ακολουθίες. Ένα τέτοιο σύνολο ακολουθιών λέγεται καθολική παρεμπόδιση για την παράμετρο (και μπορούμε επίσης να αναφερθούμε και στις ίδιες τις ακολουθίες ως καθολικές παρεμποδίσεις για την παράμετρο), αν είναι πεπερασμένο και οι ακολουθίες είναι αύξουσες ως προς τη σχέση του ελάσσονος και δεν περιέχουν η μία την άλλη ασυμπτωτικά. Σε αυτή τη διπλωματική εργασία, μελετάμε την παράμετρο της εξωεπιπεδότητας και βρίσκουμε μία οικογένεια με επτά καθολικές παρεμποδίσεις για αυτή.","abstract_has_math":false,"creators":["Λάρδας Εμμανουήλ","Lardas Emmanouil"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-08-21T16:41:59Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5425499"],"render_values":[{"text":"uoadl:5425499","href":null,"code":true}]}]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5425499","outbound_label":"Repository record","outbound_source":"dc:identifier"},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A5425499","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Λάρδας Εμμανουήλ","Lardas Emmanouil"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5425499","https://pergamos.lib.uoa.gr/uoa/dl/object/5425499"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Το κίνητρο αυτής της διπλωματικής εργασίας έγκειται στα πρόσφατα αποτελέσματα του Paul, του Πρωτόπαπα και του Θηλυκού, οι οποίοι πρότειναν ένα παραμετρικό πλαίσιο για τη μελέτη των γραφημάτων και των κλάσεων γραφημάτων. Η μελέτη των ελασσόνων γραφημάτων έχει οδηγήσει σε πολλά αλγοριθμικά και δομικά αποτελέσματα. Συχνά, όταν μελετάμε τη σχέση των ελάσσονων γραφημάτων, μας ενδιαφέρει το σύνολο των παρεμποδίσεων μία κλάσης γραφημάτων που είναι κλειστή ως προς ελάσσονα. Αν έχουμε μία τέτοια κλάση, τότε το σύνολο των παρεμποδίσεων ως προς ελάσσονα αυτής είναι το σύνολο των ελαχιστικών, ως προς τη σχέση του ελάσσονος, γραφημάτων που δεν ανήκουν στην κλάση. Είναι εύκολο να δει κανείς ότι ένα γράφημα ανήκει στην κλάση, αν και μόνο αν δεν περιέχει κανένα έλασσον που να είναι ισόμορφο με μία παρεμπόδιση της κλάσης. Το Θεώρημα των Robertson-Seymour συνεπάγεται ότι αυτό το σύνολο παρεμποδίσεων είναι πεπερασμένο (αν ταυτίσουμε ισόμορφα γραφήματα) για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα. Είναι, επιπλέον, γνωστό ότι το να ελέγξουμε αν ένα συγκεκριμένο γράφημα είναι ισόμορφο με κάποιο έλασσον ενός δοθέντος γραφήματος μπορεί να γίνει σε πολυωνυμικό χρόνο ως προς το μέγεθος του δεύτερου. Έτσι, το Θεώρημα των Robertson-Seymour συνεπάγεται ότι, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα, υπάρχει αλγόριθμος πολυωνυμικού χρόνου που ελέγχει αν η είσοδός του ανήκει σε εκείνη την κλάση. Ένα πρόβλημα με αυτή την προσέγγιση είναι ότι συχνά είναι δύσκολο να αναγνωριστούν ακριβώς οι παρεμποδίσεις μίας δοθείσας κλάσης. Όμως, οι κλάσεις για τις οποίες ενδιαφερόμαστε μπορούν συχνά να περιγραφούν ως κλάσεις όπου κάποια παράμετρος γραφημάτων είναι φραγμένη από μία συγκεκριμένη σταθερά. Αυτή η ιδέα βρίσκεται στα θεμέλια των πρόσφατων εργασιών του Paul, του Πρωτόπαπα και του Θηλυκού, όπου οι συγγραφείς ορίζουν ένα πλαίσιο που μας βοηθά να φράξουμε παραμέτρους ασυμπτωτικά. Υπό αυτό το πλαίσιο, ενδιαφερόμαστε πλέον για ακολουθίες γραφημάτων, τέτοιες ώστε μία δοθείσα παράμετρος να είναι μεγάλη σε ένα γράφημα, αν και μόνο αν το γράφημα περιέχει κάποιο έλασσον που να είναι ισόμορφο με κάποιο μεγάλο μέλος μίας από αυτές τις ακολουθίες. Ένα τέτοιο σύνολο ακολουθιών λέγεται καθολική παρεμπόδιση για την παράμετρο (και μπορούμε επίσης να αναφερθούμε και στις ίδιες τις ακολουθίες ως καθολικές παρεμποδίσεις για την παράμετρο), αν είναι πεπερασμένο και οι ακολουθίες είναι αύξουσες ως προς τη σχέση του ελάσσονος και δεν περιέχουν η μία την άλλη ασυμπτωτικά. Σε αυτή τη διπλωματική εργασία, μελετάμε την παράμετρο της εξωεπιπεδότητας και βρίσκουμε μία οικογένεια με επτά καθολικές παρεμποδίσεις για αυτή.","This thesis is motivated by the recent results of Paul, Protopapas and Thilikos, where the authors proposed a parametric framework for studying graphs and graph classes. The study of graph minors has led to many algorithmic and structural results. Often, when working with the graph minor relation, we are interested in the obstruction set of some minor-closed graph class. If we have such a class, then the set of minor-obstructions of that class is the set of minor-minimal graphs that are not in the class. It is easy to see that a graph is in the class if and only if it does not contain any minor isomorphic to an obstruction of the class. The Robertson-Seymour Theorem implies that this set of obstructions is finite (if we identify isomorphic graphs) for every minor-closed graph class. Additionally, it is well known that checking if a specific graph is isomorphic to a minor of a given graph can be done in polynomial time with respect to the size of the latter. Therefore, the Robertson-Seymour Theorem implies that, for every minor-closed graph class, there exists a polynomial-time algorithm to check for membership in that class. One problem with this approach is that it is often difficult to precisely identify the obstructions of a given class. However, the classes we are interested can often be described as classes where some graph parameter is bounded by a specific constant. This concept is the foundation for the recent work of Paul, Protopapas and Thilikos, where the authors define a framework that helps us bound graph parameters asymptotically. Under this framework, we are now interested in sequences of graphs, such that a given parameter is large in a graph if and only if the graph contains a minor that is isomorphic to a large member of one of these sequences. Such a set of sequences is called a universal obstruction for the parameter (and the sequences themselves may also be referred to as universal obstructions for the parameter) if it is finite and the sequences are minor-increasing and do not contain each other asymptotically. In this thesis, we study the parameter of outerplanarity and identify a family of seven universal obstructions for it."]},{"key":"dc:title","label":"Title","values":["Universal Obstructions for Outerplanarity"]}]}],"canonical_facts":{"dc:creator":["Λάρδας Εμμανουήλ","Lardas Emmanouil"],"dc:date":["2026"],"dc:description":["Το κίνητρο αυτής της διπλωματικής εργασίας έγκειται στα πρόσφατα αποτελέσματα του Paul, του Πρωτόπαπα και του Θηλυκού, οι οποίοι πρότειναν ένα παραμετρικό πλαίσιο για τη μελέτη των γραφημάτων και των κλάσεων γραφημάτων. Η μελέτη των ελασσόνων γραφημάτων έχει οδηγήσει σε πολλά αλγοριθμικά και δομικά αποτελέσματα. Συχνά, όταν μελετάμε τη σχέση των ελάσσονων γραφημάτων, μας ενδιαφέρει το σύνολο των παρεμποδίσεων μία κλάσης γραφημάτων που είναι κλειστή ως προς ελάσσονα. Αν έχουμε μία τέτοια κλάση, τότε το σύνολο των παρεμποδίσεων ως προς ελάσσονα αυτής είναι το σύνολο των ελαχιστικών, ως προς τη σχέση του ελάσσονος, γραφημάτων που δεν ανήκουν στην κλάση. Είναι εύκολο να δει κανείς ότι ένα γράφημα ανήκει στην κλάση, αν και μόνο αν δεν περιέχει κανένα έλασσον που να είναι ισόμορφο με μία παρεμπόδιση της κλάσης. Το Θεώρημα των Robertson-Seymour συνεπάγεται ότι αυτό το σύνολο παρεμποδίσεων είναι πεπερασμένο (αν ταυτίσουμε ισόμορφα γραφήματα) για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα. Είναι, επιπλέον, γνωστό ότι το να ελέγξουμε αν ένα συγκεκριμένο γράφημα είναι ισόμορφο με κάποιο έλασσον ενός δοθέντος γραφήματος μπορεί να γίνει σε πολυωνυμικό χρόνο ως προς το μέγεθος του δεύτερου. Έτσι, το Θεώρημα των Robertson-Seymour συνεπάγεται ότι, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελάσσονα, υπάρχει αλγόριθμος πολυωνυμικού χρόνου που ελέγχει αν η είσοδός του ανήκει σε εκείνη την κλάση. Ένα πρόβλημα με αυτή την προσέγγιση είναι ότι συχνά είναι δύσκολο να αναγνωριστούν ακριβώς οι παρεμποδίσεις μίας δοθείσας κλάσης. Όμως, οι κλάσεις για τις οποίες ενδιαφερόμαστε μπορούν συχνά να περιγραφούν ως κλάσεις όπου κάποια παράμετρος γραφημάτων είναι φραγμένη από μία συγκεκριμένη σταθερά. Αυτή η ιδέα βρίσκεται στα θεμέλια των πρόσφατων εργασιών του Paul, του Πρωτόπαπα και του Θηλυκού, όπου οι συγγραφείς ορίζουν ένα πλαίσιο που μας βοηθά να φράξουμε παραμέτρους ασυμπτωτικά. Υπό αυτό το πλαίσιο, ενδιαφερόμαστε πλέον για ακολουθίες γραφημάτων, τέτοιες ώστε μία δοθείσα παράμετρος να είναι μεγάλη σε ένα γράφημα, αν και μόνο αν το γράφημα περιέχει κάποιο έλασσον που να είναι ισόμορφο με κάποιο μεγάλο μέλος μίας από αυτές τις ακολουθίες. Ένα τέτοιο σύνολο ακολουθιών λέγεται καθολική παρεμπόδιση για την παράμετρο (και μπορούμε επίσης να αναφερθούμε και στις ίδιες τις ακολουθίες ως καθολικές παρεμποδίσεις για την παράμετρο), αν είναι πεπερασμένο και οι ακολουθίες είναι αύξουσες ως προς τη σχέση του ελάσσονος και δεν περιέχουν η μία την άλλη ασυμπτωτικά. Σε αυτή τη διπλωματική εργασία, μελετάμε την παράμετρο της εξωεπιπεδότητας και βρίσκουμε μία οικογένεια με επτά καθολικές παρεμποδίσεις για αυτή.","This thesis is motivated by the recent results of Paul, Protopapas and Thilikos, where the authors proposed a parametric framework for studying graphs and graph classes. The study of graph minors has led to many algorithmic and structural results. Often, when working with the graph minor relation, we are interested in the obstruction set of some minor-closed graph class. If we have such a class, then the set of minor-obstructions of that class is the set of minor-minimal graphs that are not in the class. It is easy to see that a graph is in the class if and only if it does not contain any minor isomorphic to an obstruction of the class. The Robertson-Seymour Theorem implies that this set of obstructions is finite (if we identify isomorphic graphs) for every minor-closed graph class. Additionally, it is well known that checking if a specific graph is isomorphic to a minor of a given graph can be done in polynomial time with respect to the size of the latter. Therefore, the Robertson-Seymour Theorem implies that, for every minor-closed graph class, there exists a polynomial-time algorithm to check for membership in that class. One problem with this approach is that it is often difficult to precisely identify the obstructions of a given class. However, the classes we are interested can often be described as classes where some graph parameter is bounded by a specific constant. This concept is the foundation for the recent work of Paul, Protopapas and Thilikos, where the authors define a framework that helps us bound graph parameters asymptotically. Under this framework, we are now interested in sequences of graphs, such that a given parameter is large in a graph if and only if the graph contains a minor that is isomorphic to a large member of one of these sequences. Such a set of sequences is called a universal obstruction for the parameter (and the sequences themselves may also be referred to as universal obstructions for the parameter) if it is finite and the sequences are minor-increasing and do not contain each other asymptotically. In this thesis, we study the parameter of outerplanarity and identify a family of seven universal obstructions for it."],"dc:identifier":["uoadl:5425499","https://pergamos.lib.uoa.gr/uoa/dl/object/5425499"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Universal Obstructions for Outerplanarity"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-08-21T16:41:59Z"}