MSc thesis defense presentation
Dimitrios Chatzidimitriou defends his MSc thesis
|Date:||Tuesday, 04 Oct 2016|
|Location:||Univeristy of Athens, Department of Mathematics, University of Athens, room A11|
|Thesis title:||An Alternative Proof for the NP-completeness of the Grid Subgraph Problem|
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.