Font size: Αα Αα Αα hide gadgets
You are here: Defenses » October 2016 » Dimitrios Chatzidimitriou
download defense details: { pdf }

MSc thesis defense presentation

Dimitrios Chatzidimitriou defends his MSc thesis

Date: Tuesday, 04 Oct 2016
Time: 11:00
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

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.