{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321387"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321387","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Sphere-cut decompositions and dominating sets in planar graphs","abstract":"Ένα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner απο τους Neil Robertson και Paul. D. Seymour στη σειρά εργασιών \"Ελλάσονα Γραφήματα\" απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ως προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλαίσια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλάτους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής \"διαίρει και βασίλευε\". Επιπλέον εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλάση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτέλεσμα σχετικά με το κλαδοπλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor. V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ \\sqrt{4.5\\cdot n}. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θηλυκός συσχέτισε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r\\cdot\\sqrt{4.5\\cdot k}. H παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αυτού του αποτελέσματος. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος όπου το μέγεθος του είναι γραμμικό ως προς το k.","abstract_html":"Ένα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner απο τους Neil Robertson και Paul. D. Seymour στη σειρά εργασιών &quot;Ελλάσονα Γραφήματα&quot; απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ως προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλαίσια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλάτους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής &quot;διαίρει και βασίλευε&quot;. Επιπλέον εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλάση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτέλεσμα σχετικά με το κλαδοπλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor. V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ \\sqrt{4.5\\cdot n}. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θηλυκός συσχέτισε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r\\cdot\\sqrt{4.5\\cdot k}. H παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αυτού του αποτελέσματος. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος όπου το μέγεθος του είναι γραμμικό ως προς το 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:43Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321387"],"render_values":[{"text":"uoadl:1321387","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321387","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321387","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%3A1321387","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:1321387","https://pergamos.lib.uoa.gr/uoa/dl/object/1321387"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ένα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner απο τους Neil Robertson και Paul. D. Seymour στη σειρά εργασιών \"Ελλάσονα Γραφήματα\" απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ως προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλαίσια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλάτους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής \"διαίρει και βασίλευε\". Επιπλέον εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλάση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτέλεσμα σχετικά με το κλαδοπλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor. V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ \\sqrt{4.5\\cdot n}. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θηλυκός συσχέτισε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r\\cdot\\sqrt{4.5\\cdot k}. H παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αυτού του αποτελέσματος. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος όπου το μέγεθος του είναι γραμμικό ως προς το k.","An important result in Graph Theory is the proof of Wagner's Conjecture by Neil Robertson and Paul D. Seymour in Graph Minor Series from 1983 until 2011. This conjecture state that there is no in nite anti-chain in the class of graphs under the minor relation. The theory that was built for the proof of this conjecture had, and continues to have, an important impact not only in structural and algorithmic Graph Theory, but also in other elds such as Parameterized Complexity. In the context of this proof, the authors have introduced some new width parameters. Within these were branchwidth and branch decompositions. This parameter was used for algorithm design via the \\divide and conquer\" technique. Moreover, the authors have introduced, similar to branch decompositions, concepts such as sphere-cut decompositions which are a special type of branch decompositions in planar graphs that have some additional properties. In the course of the research there was a lot of important results about branchwidth in the class of planar graphs. Fedor V. Fomin and Dimitrios M. Thilikos proved that the branchwidth of a n-vertex planar graph is at most p4:5 n. Based on this result Dimitrios M. Thilikos connected the branchwidth with r-radial dominating set which is another parameter in plane graphs. He proved that if a plane graph has an r-radial dominating set of size at most k, then the branchwidth of the graph is at most r p4:5 k. The purpose of this thesis is to provide a qualitative extension of this result. What we show is that this upper bound is attained by a number of edges of a sphere-cut decomposition, that is a linear function of k."]},{"key":"dc:title","label":"Title","values":["Sphere-cut decompositions and dominating sets in planar graphs"]}]}],"canonical_facts":{"dc:creator":["Σάμαρης Μιχάλης"],"dc:date":["2016"],"dc:description":["Ένα σημαντικό αποτέλεσμα στη Θεωρία Γραφημάτων αποτελεί η απόδειξη της εικασίας του Wagner απο τους Neil Robertson και Paul. D. Seymour στη σειρά εργασιών \"Ελλάσονα Γραφήματα\" απο το 1983 εώς το 2011. Η εικασία αυτή λέει ότι στην κλάση των γραφημάτων δεν υπάρχει άπειρη αντιαλυσίδα ως προς τη σχέση των ελλασόνων γραφημάτων. Η Θεωρία που αναπτύχθηκε για την απόδειξη αυτής της εικασίας είχε και έχει ακόμα σημαντικό αντίκτυπο τόσο στην δομική όσο και στην αλγοριθμική Θεωρία Γραφημάτων, άλλα και σε άλλα πεδία όπως η Παραμετρική Πολυπλοκότητα. Στα πλαίσια της απόδειξης οι συγγραφείς εισήγαγαν και νέες παραμέτρους πλάτους. Σε αυτές ήταν η κλαδοαποσύνθεση και το κλαδοπλάτος ενός γραφήματος. Η παράμετρος αυτή χρησιμοποιήθηκε ιδιαίτερα στο σχεδιασμό αλγορίθμων και στην χρήση της τεχνικής \"διαίρει και βασίλευε\". Επιπλέον εισήχθησαν νέες παρεμφερείς έννοιες όπως οι αποσυνθέσεις σφαιρικών τομών που είναι κλαδοαποσυνθέσεις στην κλάση των επίπεδων γραφημάτων που έχουν κάποιες επιπλέον ιδιότητες. Στην εξέλιξη της έρευνας υπήρξαν σημαντικά αποτέλεσμα σχετικά με το κλαδοπλάτος στην κλάση των επίπεδων γραφημάτων. Οι Fedor. V. Fomin και Δημήτριος Μ. Θηλυκός απέδειξαν ότι το κλαδοπλάτος ενός επίπεδου γραφήματος με n κορυφές είναι το πολύ \\sqrt{4.5\\cdot n}. Βασιζόμενος σε αυτό το αποτέλεσμα, ο Δημήτριος Μ. Θηλυκός συσχέτισε το κλαδοπλάτος με μια άλλη παράμετρο σε επίπεδα γραφήματα, το r-ακτινικό σύνολο κυριαρχίας. Απέδειξε ότι αν εμβαπτισμένο επίπεδο γράφημα έχει r- ακτινικό σύνολο κυριαρχίας το πολύ k, τότε το κλαδοπλάτος του γραφήματος θα είναι το πολύ r\\cdot\\sqrt{4.5\\cdot k}. H παρούσα διπλωματική εργασία κάνει μια ποιοτική επέκταση του αυτού του αποτελέσματος. Αποδεικνύουμε ότι το παραπάνω όριο μπορεί να αναζητηθεί σε ένα δάσος που είναι υπογράφημα του δέντρου μιας αποσύνθεσης σφαιρικών τομών του γραφήματος όπου το μέγεθος του είναι γραμμικό ως προς το k.","An important result in Graph Theory is the proof of Wagner's Conjecture by Neil Robertson and Paul D. Seymour in Graph Minor Series from 1983 until 2011. This conjecture state that there is no in nite anti-chain in the class of graphs under the minor relation. The theory that was built for the proof of this conjecture had, and continues to have, an important impact not only in structural and algorithmic Graph Theory, but also in other elds such as Parameterized Complexity. In the context of this proof, the authors have introduced some new width parameters. Within these were branchwidth and branch decompositions. This parameter was used for algorithm design via the \\divide and conquer\" technique. Moreover, the authors have introduced, similar to branch decompositions, concepts such as sphere-cut decompositions which are a special type of branch decompositions in planar graphs that have some additional properties. In the course of the research there was a lot of important results about branchwidth in the class of planar graphs. Fedor V. Fomin and Dimitrios M. Thilikos proved that the branchwidth of a n-vertex planar graph is at most p4:5 n. Based on this result Dimitrios M. Thilikos connected the branchwidth with r-radial dominating set which is another parameter in plane graphs. He proved that if a plane graph has an r-radial dominating set of size at most k, then the branchwidth of the graph is at most r p4:5 k. The purpose of this thesis is to provide a qualitative extension of this result. What we show is that this upper bound is attained by a number of edges of a sphere-cut decomposition, that is a linear function of k."],"dc:identifier":["uoadl:1321387","https://pergamos.lib.uoa.gr/uoa/dl/object/1321387"],"dc:language":["English"],"dc:title":["Sphere-cut decompositions and dominating sets in planar graphs"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:43Z"}