mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » October 2016 » Dimitrios Chatzidimitriou Anonymously browsing from 54.159.113.182 at 00:19:26, 22-09-2017. login
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
Committee:

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.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

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