{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320877"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320877","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"An alternative proof for the NP-completeness of the Grid Subgraph problem","abstract":"Στον τομέα της Γραφικής Αναπαράστασης Γραφημάτων υπάρχει μεγάλο ενδιαφέρον για αποτελέσματα σχετικά με την εμβάπτιση ενός δοθέντος γραφήματος πάνω σε μία σχάρα, κυρίως λόγω των εφαρμογών στο σχεδιασμό κυκλωμάτων VLSI. Πιο συγκεκριμένα, το ερώτημα αν ένα γράφημα επιδέχεται εμβάπτιση μοναδιαίου μήκους, δηλαδή μια αντιστοίχιση των κορυφών και των ακμών του γραφήματος σε κορυφές και ακμές μιας αρκετά μεγάλης σχάρας, ταυτίζεται με το ερώτημα αν το γράφημα είναι υπογράφημα της συγκεκριμένης σχάρας. Θεωρούμε το πρόβλημα Υπογράφημα Σχάρας, στο οποίο δοθέντος ενός επίπεδου (όχι απαραίτητα συνεκτικού) γραφήματος G, καλούμαστε να αποφανθούμε αν το G είναι ισόμορφο με κάποιο υπογράφημα μιας αρκετά μεγάλης σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι προκαθορισμένο, γνωστό και ως το πρόβλημα Υπογράφημα (k *k)-Σχάρας, είναι επίσης NP-πλήρες.","abstract_html":"Στον τομέα της Γραφικής Αναπαράστασης Γραφημάτων υπάρχει μεγάλο ενδιαφέρον για αποτελέσματα σχετικά με την εμβάπτιση ενός δοθέντος γραφήματος πάνω σε μία σχάρα, κυρίως λόγω των εφαρμογών στο σχεδιασμό κυκλωμάτων VLSI. Πιο συγκεκριμένα, το ερώτημα αν ένα γράφημα επιδέχεται εμβάπτιση μοναδιαίου μήκους, δηλαδή μια αντιστοίχιση των κορυφών και των ακμών του γραφήματος σε κορυφές και ακμές μιας αρκετά μεγάλης σχάρας, ταυτίζεται με το ερώτημα αν το γράφημα είναι υπογράφημα της συγκεκριμένης σχάρας. Θεωρούμε το πρόβλημα Υπογράφημα Σχάρας, στο οποίο δοθέντος ενός επίπεδου (όχι απαραίτητα συνεκτικού) γραφήματος G, καλούμαστε να αποφανθούμε αν το G είναι ισόμορφο με κάποιο υπογράφημα μιας αρκετά μεγάλης σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι προκαθορισμένο, γνωστό και ως το πρόβλημα Υπογράφημα (k *k)-Σχάρας, είναι επίσης NP-πλήρες.","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:32Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320877"],"render_values":[{"text":"uoadl:1320877","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320877","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320877","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%3A1320877","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:1320877","https://pergamos.lib.uoa.gr/uoa/dl/object/1320877"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στον τομέα της Γραφικής Αναπαράστασης Γραφημάτων υπάρχει μεγάλο ενδιαφέρον για αποτελέσματα σχετικά με την εμβάπτιση ενός δοθέντος γραφήματος πάνω σε μία σχάρα, κυρίως λόγω των εφαρμογών στο σχεδιασμό κυκλωμάτων VLSI. Πιο συγκεκριμένα, το ερώτημα αν ένα γράφημα επιδέχεται εμβάπτιση μοναδιαίου μήκους, δηλαδή μια αντιστοίχιση των κορυφών και των ακμών του γραφήματος σε κορυφές και ακμές μιας αρκετά μεγάλης σχάρας, ταυτίζεται με το ερώτημα αν το γράφημα είναι υπογράφημα της συγκεκριμένης σχάρας. Θεωρούμε το πρόβλημα Υπογράφημα Σχάρας, στο οποίο δοθέντος ενός επίπεδου (όχι απαραίτητα συνεκτικού) γραφήματος G, καλούμαστε να αποφανθούμε αν το G είναι ισόμορφο με κάποιο υπογράφημα μιας αρκετά μεγάλης σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι προκαθορισμένο, γνωστό και ως το πρόβλημα Υπογράφημα (k *k)-Σχάρας, είναι επίσης NP-πλήρες.","In the field of Graph Drawing, there is great interest for results regarding the embedding of a given graph on a grid, mainly due to the applications on the VLSI circuit design. Moreover, determining whether a graph accepts a unit-length embedding, i.e., a matching of its vertices and edges to vertices and edges of a large enough grid, is the same as asking whether the graph is a subgraph of that grid. We consider the Grid Subgraph problem, in which given a planar (not necessarily connected) graph G, we need to determine if G is isomorphic to a subgraph of a large enough grid. We prove that this problem is NP-complete by employing simple and intuitive gadgets to perform a reduction from a SAT-variant. In addition we prove that a special case of that problem, the (k*k)-Grid Subgraph problem, in which the size of the grid is given in the input, is also NP-complete."]},{"key":"dc:title","label":"Title","values":["An alternative proof for the NP-completeness of the Grid Subgraph problem"]}]}],"canonical_facts":{"dc:creator":["Χατζηδημητρίου Δημήτριος"],"dc:date":["2016"],"dc:description":["Στον τομέα της Γραφικής Αναπαράστασης Γραφημάτων υπάρχει μεγάλο ενδιαφέρον για αποτελέσματα σχετικά με την εμβάπτιση ενός δοθέντος γραφήματος πάνω σε μία σχάρα, κυρίως λόγω των εφαρμογών στο σχεδιασμό κυκλωμάτων VLSI. Πιο συγκεκριμένα, το ερώτημα αν ένα γράφημα επιδέχεται εμβάπτιση μοναδιαίου μήκους, δηλαδή μια αντιστοίχιση των κορυφών και των ακμών του γραφήματος σε κορυφές και ακμές μιας αρκετά μεγάλης σχάρας, ταυτίζεται με το ερώτημα αν το γράφημα είναι υπογράφημα της συγκεκριμένης σχάρας. Θεωρούμε το πρόβλημα Υπογράφημα Σχάρας, στο οποίο δοθέντος ενός επίπεδου (όχι απαραίτητα συνεκτικού) γραφήματος G, καλούμαστε να αποφανθούμε αν το G είναι ισόμορφο με κάποιο υπογράφημα μιας αρκετά μεγάλης σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι προκαθορισμένο, γνωστό και ως το πρόβλημα Υπογράφημα (k *k)-Σχάρας, είναι επίσης NP-πλήρες.","In the field of Graph Drawing, there is great interest for results regarding the embedding of a given graph on a grid, mainly due to the applications on the VLSI circuit design. Moreover, determining whether a graph accepts a unit-length embedding, i.e., a matching of its vertices and edges to vertices and edges of a large enough grid, is the same as asking whether the graph is a subgraph of that grid. We consider the Grid Subgraph problem, in which given a planar (not necessarily connected) graph G, we need to determine if G is isomorphic to a subgraph of a large enough grid. We prove that this problem is NP-complete by employing simple and intuitive gadgets to perform a reduction from a SAT-variant. In addition we prove that a special case of that problem, the (k*k)-Grid Subgraph problem, in which the size of the grid is given in the input, is also NP-complete."],"dc:identifier":["uoadl:1320877","https://pergamos.lib.uoa.gr/uoa/dl/object/1320877"],"dc:language":["English"],"dc:title":["An alternative proof for the NP-completeness of the Grid Subgraph problem"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:32Z"}