mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Dimitrios Chatzidimitriou

MSc thesis of Dimitrios Chatzidimitriou

An Alternative Proof for the NP-completeness of the Grid Subgraph Problem

Supervisor: Dimitrios M. Thilikos

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.

Defended: Oct. 4, 2016.

Scientific committee

Download

Download thesis.

Reporter

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