Ο φοιτητής του προγράμματος Εμμανουήλ Λάρδας θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Universal Obstructions for Outerplanarity
την Πέμπτη 11 Ιουνίου 2026 και ώρα 11:00, στην αίθουσα Α12 στο τμ. Μαθηματικών του ΕΚΠΑ
Σύνοψη Διπλωματικής:
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, who proposed a parametric 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 7 universal obstructions for it.
Η επιτροπή,
Αρχοντία Χ. Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Ε.Κ.Π.Α.
Δημήτρης Ζώρος (Επιβλέπων),
Εξωτερικός Συνεργάτης
Δημήτριος Μ. Θηλυκός,
Τμήμα Μαθηματικών Ε.Κ.Π.Α.