{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321199"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321199","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Linkages in primal-dual graphs","abstract":"Ένα από τα επιτεύγματα με τη μεγαλύτερη επιρροή στη Θεωρία Γραφημάτων υπήρξε χωρίς αμφιβολία η σειρά εργασιών \"Ελλάσσονα Γραφήματα\" των Neil Robertson και Paul D. Seymour, στην οποία, έπειτα από 23 εργασίες από το 1983 έως το 2011, κατάφεραν να αποδείξουν την εικασία του Wagner. Η εικασία αυτή λέει ότι η κλάση των μη κατευθυνόμενων γραφημάτων, μερικώς διατεταγμένων με τη σχέση ελλάσσονος γραφήματος, αποτελεί well-quasi- διάταξη ή ισοδύναμα, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελλάσσονα υπάρχει ένα σύνολο από απαγορευμένα γραφήματα ως ελλάσσονα. Μπορεί να υποστηριχθεί ότι, δεν είναι τόσο το ίδιο το τελικό αποτέλεσμα, όσο ολόκληρη η θεωρία που αναπτύχθηκε στην πορεία που είχε, και συνεχίζει να έχει, τεράστιο αντίκτυπο τόσο στη συνδυαστική όσο και στην αλγοριθμική Θεωρία Γραφημάτων. Μία από τις κυριότερες συνεισφορές τους, η οποία κατέχει και κεντρικό ρόλο στη δουλειά τους, είναι η κατασκευή ενός αλγορίθμου που λύνει το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ σε χρόνο f(k)n^3, όπου k είναι το πλήθος των διακεκριμένων μονοπατιών που μας ζητείται να βρούμε. Το βασικό συστατικό της απόδειξής τους είναι η ονομαστή τεχνική της άσχετης κορυφής (για την οποία οι πλήρεις αποδείξεις δόθηκαν σε επόμενο μέρος της σειράς) που χρησιμοποιήθηκε ευρέως στην πορεία. Όσο σπουδαίο κι αν αποδείχθηκε πως είναι το παραπάνω αποτέλεσμα, η συνάρτηση f που εξαρτάται από το k και εμφανίζεται στη χρονική πολυπλοκό- τητα του αλγορίθμου, είναι ασύλληπτα μεγάλη ακόμη και για πολύ μικρές τιμές του k. Για τον λόγο αυτόν, πολλοί ερευνητές θέλησαν να βελτιώσουν αυτήν την παραμετρική εξάρτηση από το k, είτε προσπαθώντας να απλοποιήσουν τις περίπλοκες αποδείξεις των δομικών θεωρημάτων για τη γενική περίπτωση, είτε επικεντρώνοντας την προσοχή τους σε συγκεκριμένες κλάσεις γραφημάτων των οποίων τα δομικά χαρακτηριστικά θα οδηγούσαν, ίσως, σε απλούστερες αποδείξεις και καλύτερη παραμετρική εξάρτηση. Ένα μεγάλο βήμα όσον αφορά την πρώτη κατεύθυνση (παρόλο που το φράγμα για το f(k) είναι 2^(2^(2^(2^Ω(k)))) , το οποίο είναι, σαφώς, ακόμη τεράστιο) έγινε από τους Ken-ichi Kawarabayashi και Paul Wollan στο [20]. Ένα αποφασιστικό βήμα προς τη δεύτερη κατεύθυνση, για την κλάση των επίπεδων γραφημάτων, έγινε από τους Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, και Dimitrios M. Thilikos στο [2], όπου αποδεικνύουν ένα φράγμα για το f(k) που είναι απλά εκθετικό ως προς k. Βασιζόμενοι σε αυτήν την τελευταία εργασία, μελετάμε μια επέκταση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ στην κλάση των πρωτεύοντων- δυϊκών γραφημάτων και χρησιμοποιώντας την ιδέα άσχετης κορυφής, αποδεικ- νύουμε ένα δομικό θεώρημα το οποίο λέει ότι αν το δεντροπλάτος του πρωτεύοντος- δυϊκού γραφήματος μας είναι αρκούντως μεγάλο, τότε υπάρχει (και μπορεί να εντοπιστεί αλγοριθμικά) ένα τμήμα του το οποίο είναι άσχετο και του οποίου η αφαίρεση από το γράφημα οδηγεί σε ένα απλούστερο και ισοδύναμο στιγμιότυπο του προβλήματος. Επίσης, εξηγούμε πως ένας αλγόριθμος για το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ για την κλάση των πρωτεύοντων-δυϊκών γραφημάτων μπορεί να χρησιμοποιηθεί για την κατασκευή αλγορίθμων για προ- βλήματα σε ενεπίπεδα γραφήματα, όπου είναι απαραίτητο να λαμβάνεται υπόψην η τοπολογία της επίπεδης εμβάπτισης που δίνεται ως είσοδος.","abstract_html":"Ένα από τα επιτεύγματα με τη μεγαλύτερη επιρροή στη Θεωρία Γραφημάτων υπήρξε χωρίς αμφιβολία η σειρά εργασιών &quot;Ελλάσσονα Γραφήματα&quot; των Neil Robertson και Paul D. Seymour, στην οποία, έπειτα από 23 εργασίες από το 1983 έως το 2011, κατάφεραν να αποδείξουν την εικασία του Wagner. Η εικασία αυτή λέει ότι η κλάση των μη κατευθυνόμενων γραφημάτων, μερικώς διατεταγμένων με τη σχέση ελλάσσονος γραφήματος, αποτελεί well-quasi- διάταξη ή ισοδύναμα, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελλάσσονα υπάρχει ένα σύνολο από απαγορευμένα γραφήματα ως ελλάσσονα. Μπορεί να υποστηριχθεί ότι, δεν είναι τόσο το ίδιο το τελικό αποτέλεσμα, όσο ολόκληρη η θεωρία που αναπτύχθηκε στην πορεία που είχε, και συνεχίζει να έχει, τεράστιο αντίκτυπο τόσο στη συνδυαστική όσο και στην αλγοριθμική Θεωρία Γραφημάτων. Μία από τις κυριότερες συνεισφορές τους, η οποία κατέχει και κεντρικό ρόλο στη δουλειά τους, είναι η κατασκευή ενός αλγορίθμου που λύνει το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ σε χρόνο f(k)n^3, όπου k είναι το πλήθος των διακεκριμένων μονοπατιών που μας ζητείται να βρούμε. Το βασικό συστατικό της απόδειξής τους είναι η ονομαστή τεχνική της άσχετης κορυφής (για την οποία οι πλήρεις αποδείξεις δόθηκαν σε επόμενο μέρος της σειράς) που χρησιμοποιήθηκε ευρέως στην πορεία. Όσο σπουδαίο κι αν αποδείχθηκε πως είναι το παραπάνω αποτέλεσμα, η συνάρτηση f που εξαρτάται από το k και εμφανίζεται στη χρονική πολυπλοκό- τητα του αλγορίθμου, είναι ασύλληπτα μεγάλη ακόμη και για πολύ μικρές τιμές του k. Για τον λόγο αυτόν, πολλοί ερευνητές θέλησαν να βελτιώσουν αυτήν την παραμετρική εξάρτηση από το k, είτε προσπαθώντας να απλοποιήσουν τις περίπλοκες αποδείξεις των δομικών θεωρημάτων για τη γενική περίπτωση, είτε επικεντρώνοντας την προσοχή τους σε συγκεκριμένες κλάσεις γραφημάτων των οποίων τα δομικά χαρακτηριστικά θα οδηγούσαν, ίσως, σε απλούστερες αποδείξεις και καλύτερη παραμετρική εξάρτηση. Ένα μεγάλο βήμα όσον αφορά την πρώτη κατεύθυνση (παρόλο που το φράγμα για το f(k) είναι 2^(2^(2^(2^Ω(k)))) , το οποίο είναι, σαφώς, ακόμη τεράστιο) έγινε από τους Ken-ichi Kawarabayashi και Paul Wollan στο [20]. Ένα αποφασιστικό βήμα προς τη δεύτερη κατεύθυνση, για την κλάση των επίπεδων γραφημάτων, έγινε από τους Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, και Dimitrios M. Thilikos στο [2], όπου αποδεικνύουν ένα φράγμα για το f(k) που είναι απλά εκθετικό ως προς k. Βασιζόμενοι σε αυτήν την τελευταία εργασία, μελετάμε μια επέκταση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ στην κλάση των πρωτεύοντων- δυϊκών γραφημάτων και χρησιμοποιώντας την ιδέα άσχετης κορυφής, αποδεικ- νύουμε ένα δομικό θεώρημα το οποίο λέει ότι αν το δεντροπλάτος του πρωτεύοντος- δυϊκού γραφήματος μας είναι αρκούντως μεγάλο, τότε υπάρχει (και μπορεί να εντοπιστεί αλγοριθμικά) ένα τμήμα του το οποίο είναι άσχετο και του οποίου η αφαίρεση από το γράφημα οδηγεί σε ένα απλούστερο και ισοδύναμο στιγμιότυπο του προβλήματος. Επίσης, εξηγούμε πως ένας αλγόριθμος για το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ για την κλάση των πρωτεύοντων-δυϊκών γραφημάτων μπορεί να χρησιμοποιηθεί για την κατασκευή αλγορίθμων για προ- βλήματα σε ενεπίπεδα γραφήματα, όπου είναι απαραίτητο να λαμβάνεται υπόψην η τοπολογία της επίπεδης εμβάπτισης που δίνεται ως είσοδος.","abstract_has_math":false,"creators":["Μανιάτης Σπυρίδων"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-11-19T05:26:40Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321199"],"render_values":[{"text":"uoadl:1321199","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321199","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321199","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321199","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Μανιάτης Σπυρίδων"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"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:1321199","https://pergamos.lib.uoa.gr/uoa/dl/object/1321199"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ένα από τα επιτεύγματα με τη μεγαλύτερη επιρροή στη Θεωρία Γραφημάτων υπήρξε χωρίς αμφιβολία η σειρά εργασιών \"Ελλάσσονα Γραφήματα\" των Neil Robertson και Paul D. Seymour, στην οποία, έπειτα από 23 εργασίες από το 1983 έως το 2011, κατάφεραν να αποδείξουν την εικασία του Wagner. Η εικασία αυτή λέει ότι η κλάση των μη κατευθυνόμενων γραφημάτων, μερικώς διατεταγμένων με τη σχέση ελλάσσονος γραφήματος, αποτελεί well-quasi- διάταξη ή ισοδύναμα, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελλάσσονα υπάρχει ένα σύνολο από απαγορευμένα γραφήματα ως ελλάσσονα. Μπορεί να υποστηριχθεί ότι, δεν είναι τόσο το ίδιο το τελικό αποτέλεσμα, όσο ολόκληρη η θεωρία που αναπτύχθηκε στην πορεία που είχε, και συνεχίζει να έχει, τεράστιο αντίκτυπο τόσο στη συνδυαστική όσο και στην αλγοριθμική Θεωρία Γραφημάτων. Μία από τις κυριότερες συνεισφορές τους, η οποία κατέχει και κεντρικό ρόλο στη δουλειά τους, είναι η κατασκευή ενός αλγορίθμου που λύνει το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ σε χρόνο f(k)n^3, όπου k είναι το πλήθος των διακεκριμένων μονοπατιών που μας ζητείται να βρούμε. Το βασικό συστατικό της απόδειξής τους είναι η ονομαστή τεχνική της άσχετης κορυφής (για την οποία οι πλήρεις αποδείξεις δόθηκαν σε επόμενο μέρος της σειράς) που χρησιμοποιήθηκε ευρέως στην πορεία. Όσο σπουδαίο κι αν αποδείχθηκε πως είναι το παραπάνω αποτέλεσμα, η συνάρτηση f που εξαρτάται από το k και εμφανίζεται στη χρονική πολυπλοκό- τητα του αλγορίθμου, είναι ασύλληπτα μεγάλη ακόμη και για πολύ μικρές τιμές του k. Για τον λόγο αυτόν, πολλοί ερευνητές θέλησαν να βελτιώσουν αυτήν την παραμετρική εξάρτηση από το k, είτε προσπαθώντας να απλοποιήσουν τις περίπλοκες αποδείξεις των δομικών θεωρημάτων για τη γενική περίπτωση, είτε επικεντρώνοντας την προσοχή τους σε συγκεκριμένες κλάσεις γραφημάτων των οποίων τα δομικά χαρακτηριστικά θα οδηγούσαν, ίσως, σε απλούστερες αποδείξεις και καλύτερη παραμετρική εξάρτηση. Ένα μεγάλο βήμα όσον αφορά την πρώτη κατεύθυνση (παρόλο που το φράγμα για το f(k) είναι 2^(2^(2^(2^Ω(k)))) , το οποίο είναι, σαφώς, ακόμη τεράστιο) έγινε από τους Ken-ichi Kawarabayashi και Paul Wollan στο [20]. Ένα αποφασιστικό βήμα προς τη δεύτερη κατεύθυνση, για την κλάση των επίπεδων γραφημάτων, έγινε από τους Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, και Dimitrios M. Thilikos στο [2], όπου αποδεικνύουν ένα φράγμα για το f(k) που είναι απλά εκθετικό ως προς k. Βασιζόμενοι σε αυτήν την τελευταία εργασία, μελετάμε μια επέκταση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ στην κλάση των πρωτεύοντων- δυϊκών γραφημάτων και χρησιμοποιώντας την ιδέα άσχετης κορυφής, αποδεικ- νύουμε ένα δομικό θεώρημα το οποίο λέει ότι αν το δεντροπλάτος του πρωτεύοντος- δυϊκού γραφήματος μας είναι αρκούντως μεγάλο, τότε υπάρχει (και μπορεί να εντοπιστεί αλγοριθμικά) ένα τμήμα του το οποίο είναι άσχετο και του οποίου η αφαίρεση από το γράφημα οδηγεί σε ένα απλούστερο και ισοδύναμο στιγμιότυπο του προβλήματος. Επίσης, εξηγούμε πως ένας αλγόριθμος για το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ για την κλάση των πρωτεύοντων-δυϊκών γραφημάτων μπορεί να χρησιμοποιηθεί για την κατασκευή αλγορίθμων για προ- βλήματα σε ενεπίπεδα γραφήματα, όπου είναι απαραίτητο να λαμβάνεται υπόψην η τοπολογία της επίπεδης εμβάπτισης που δίνεται ως είσοδος.","One of the most influential bodies of work in Graph Theory has, undoubtedly, been the Graph Minor series of Neil Robertson and Paul D. Seymour, where, after 23 papers during the years 1983-2011, they managed to prove Wagner's conjecture. This conjecture states that undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering, or, equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors. One can argue that it is not just the final result itself, but whole theory built during the procedure which had, and continues to have, a huge impact in both combinatorial and algorithmic Graph Theory. One of their main contributions, which also has a central role in their work, is constructing an algorithm that solves the Disjoint Paths problem in f(k)n^3 steps, where k is the number of disjoint paths that we are asked to find. The key ingredient of their proof is the so called irrelevant-vertex technique (for which full proofs only appeared in latter parts of the series), which has been used extensively thereafter. As great as this result was proved to be, the function f of k that appears in the running time is immense even for very small values of k. Therefore, many researchers tried to improve this parametric dependance on k, either by trying to simplify the complicated proofs of the structural theorems for the general case, or by restricting their attention to specific graph classes whose structural characteristics would hopefully lead to simpler proofs and better parametric dependance. A big step towards the first direction (although the bound of f(k) is 2^(2^(2^(2^Ω(k)))) which is of course still huge) was made by Ken-ichi Kawarabayashi and Paul Wollan in [20]. A decisive step to the second direction, for the class of planar graphs, was made by Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos in [2], where their bound for f(k) is just single exponential on k. Based on this latter work, we study an extension of the Disjoint Paths problem for the class of pd-graphs and, using on the idea of the irrelevant-vertex technique, we prove a structural theorem which states that if the treewidth of our pd-graph is sufficiently large, then there exists (and can be found algorithmically) a part of it which is irrelevant and whose removal leads to a simpler and equivalent instance. We also illustrate how an algorithm for the Disjoint Paths problem for the class of pd-graphs can be used to construct algorithms for problems on plane graphs, where the it is essential to respect the topology of the plane embedding given as an input."]},{"key":"dc:title","label":"Title","values":["Linkages in primal-dual graphs"]}]}],"canonical_facts":{"dc:creator":["Μανιάτης Σπυρίδων"],"dc:date":["2016"],"dc:description":["Ένα από τα επιτεύγματα με τη μεγαλύτερη επιρροή στη Θεωρία Γραφημάτων υπήρξε χωρίς αμφιβολία η σειρά εργασιών \"Ελλάσσονα Γραφήματα\" των Neil Robertson και Paul D. Seymour, στην οποία, έπειτα από 23 εργασίες από το 1983 έως το 2011, κατάφεραν να αποδείξουν την εικασία του Wagner. Η εικασία αυτή λέει ότι η κλάση των μη κατευθυνόμενων γραφημάτων, μερικώς διατεταγμένων με τη σχέση ελλάσσονος γραφήματος, αποτελεί well-quasi- διάταξη ή ισοδύναμα, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελλάσσονα υπάρχει ένα σύνολο από απαγορευμένα γραφήματα ως ελλάσσονα. Μπορεί να υποστηριχθεί ότι, δεν είναι τόσο το ίδιο το τελικό αποτέλεσμα, όσο ολόκληρη η θεωρία που αναπτύχθηκε στην πορεία που είχε, και συνεχίζει να έχει, τεράστιο αντίκτυπο τόσο στη συνδυαστική όσο και στην αλγοριθμική Θεωρία Γραφημάτων. Μία από τις κυριότερες συνεισφορές τους, η οποία κατέχει και κεντρικό ρόλο στη δουλειά τους, είναι η κατασκευή ενός αλγορίθμου που λύνει το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ σε χρόνο f(k)n^3, όπου k είναι το πλήθος των διακεκριμένων μονοπατιών που μας ζητείται να βρούμε. Το βασικό συστατικό της απόδειξής τους είναι η ονομαστή τεχνική της άσχετης κορυφής (για την οποία οι πλήρεις αποδείξεις δόθηκαν σε επόμενο μέρος της σειράς) που χρησιμοποιήθηκε ευρέως στην πορεία. Όσο σπουδαίο κι αν αποδείχθηκε πως είναι το παραπάνω αποτέλεσμα, η συνάρτηση f που εξαρτάται από το k και εμφανίζεται στη χρονική πολυπλοκό- τητα του αλγορίθμου, είναι ασύλληπτα μεγάλη ακόμη και για πολύ μικρές τιμές του k. Για τον λόγο αυτόν, πολλοί ερευνητές θέλησαν να βελτιώσουν αυτήν την παραμετρική εξάρτηση από το k, είτε προσπαθώντας να απλοποιήσουν τις περίπλοκες αποδείξεις των δομικών θεωρημάτων για τη γενική περίπτωση, είτε επικεντρώνοντας την προσοχή τους σε συγκεκριμένες κλάσεις γραφημάτων των οποίων τα δομικά χαρακτηριστικά θα οδηγούσαν, ίσως, σε απλούστερες αποδείξεις και καλύτερη παραμετρική εξάρτηση. Ένα μεγάλο βήμα όσον αφορά την πρώτη κατεύθυνση (παρόλο που το φράγμα για το f(k) είναι 2^(2^(2^(2^Ω(k)))) , το οποίο είναι, σαφώς, ακόμη τεράστιο) έγινε από τους Ken-ichi Kawarabayashi και Paul Wollan στο [20]. Ένα αποφασιστικό βήμα προς τη δεύτερη κατεύθυνση, για την κλάση των επίπεδων γραφημάτων, έγινε από τους Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, και Dimitrios M. Thilikos στο [2], όπου αποδεικνύουν ένα φράγμα για το f(k) που είναι απλά εκθετικό ως προς k. Βασιζόμενοι σε αυτήν την τελευταία εργασία, μελετάμε μια επέκταση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ στην κλάση των πρωτεύοντων- δυϊκών γραφημάτων και χρησιμοποιώντας την ιδέα άσχετης κορυφής, αποδεικ- νύουμε ένα δομικό θεώρημα το οποίο λέει ότι αν το δεντροπλάτος του πρωτεύοντος- δυϊκού γραφήματος μας είναι αρκούντως μεγάλο, τότε υπάρχει (και μπορεί να εντοπιστεί αλγοριθμικά) ένα τμήμα του το οποίο είναι άσχετο και του οποίου η αφαίρεση από το γράφημα οδηγεί σε ένα απλούστερο και ισοδύναμο στιγμιότυπο του προβλήματος. Επίσης, εξηγούμε πως ένας αλγόριθμος για το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ για την κλάση των πρωτεύοντων-δυϊκών γραφημάτων μπορεί να χρησιμοποιηθεί για την κατασκευή αλγορίθμων για προ- βλήματα σε ενεπίπεδα γραφήματα, όπου είναι απαραίτητο να λαμβάνεται υπόψην η τοπολογία της επίπεδης εμβάπτισης που δίνεται ως είσοδος.","One of the most influential bodies of work in Graph Theory has, undoubtedly, been the Graph Minor series of Neil Robertson and Paul D. Seymour, where, after 23 papers during the years 1983-2011, they managed to prove Wagner's conjecture. This conjecture states that undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering, or, equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors. One can argue that it is not just the final result itself, but whole theory built during the procedure which had, and continues to have, a huge impact in both combinatorial and algorithmic Graph Theory. One of their main contributions, which also has a central role in their work, is constructing an algorithm that solves the Disjoint Paths problem in f(k)n^3 steps, where k is the number of disjoint paths that we are asked to find. The key ingredient of their proof is the so called irrelevant-vertex technique (for which full proofs only appeared in latter parts of the series), which has been used extensively thereafter. As great as this result was proved to be, the function f of k that appears in the running time is immense even for very small values of k. Therefore, many researchers tried to improve this parametric dependance on k, either by trying to simplify the complicated proofs of the structural theorems for the general case, or by restricting their attention to specific graph classes whose structural characteristics would hopefully lead to simpler proofs and better parametric dependance. A big step towards the first direction (although the bound of f(k) is 2^(2^(2^(2^Ω(k)))) which is of course still huge) was made by Ken-ichi Kawarabayashi and Paul Wollan in [20]. A decisive step to the second direction, for the class of planar graphs, was made by Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos in [2], where their bound for f(k) is just single exponential on k. Based on this latter work, we study an extension of the Disjoint Paths problem for the class of pd-graphs and, using on the idea of the irrelevant-vertex technique, we prove a structural theorem which states that if the treewidth of our pd-graph is sufficiently large, then there exists (and can be found algorithmically) a part of it which is irrelevant and whose removal leads to a simpler and equivalent instance. We also illustrate how an algorithm for the Disjoint Paths problem for the class of pd-graphs can be used to construct algorithms for problems on plane graphs, where the it is essential to respect the topology of the plane embedding given as an input."],"dc:identifier":["uoadl:1321199","https://pergamos.lib.uoa.gr/uoa/dl/object/1321199"],"dc:language":["English"],"dc:title":["Linkages in primal-dual graphs"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:40Z"}