Font size: Αα Αα Αα hide gadgets
You are here: Defenses » Οκτώβριος 2016 » Δημήτριος Χατζηδημητρίου
download defense details: { pdf }

MSc thesis defense presentation

Δημήτριος Χατζηδημητρίου defends his MSc thesis

Date: Τρίτη, 04 Οκτ 2016
Ώρα: 11:00
Location: Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, Τμήμα Μαθηματικών, room A11
Thesis title: An Alternative Proof for the NP-completeness of the Grid Subgraph Problem

Thesis abstract

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 x k)-Grid Subgraph problem, in which the size of the grid is given in the input, is also NP-complete.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.