Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Dimitrios Chatzidimitriou Anonymously browsing from at 00:11:56, 24-05-2019. login

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 thesis.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2019 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.