### Interdisciplinary Seminar Series

Title: Faithful Representations of Graphs by Islands in the Extended Grid

Speaker: **Tomas Vyskocil**, Charles University, Prague

Date: Monday, April 12, 2010 12:00 - 1:00 pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We investigate embeddings of graphs into the so called extended grid.
The extended grid graph is the planar square grid with diagonal edges
added. Our embedding is such that vertices are represented by sets
of adjacent vertices (we call them islands) of the grid and two
vertices are connected by an edge if the corresponding islands are
adjacent (along a vertical, horizontal or diagonal edge).
This problem is motivated by computation on adiabatic quantum
computers.

As defined above, we are simply interested in induced minors of the
extended grid. However, also stemming from the motivation, we pose
a more restricted question of representing graphs by islands of restricted
size. We conjecture that for all k>= 1, deciding if an input graph can
be represented by islands of size at most k is NP-complete, and prove
this conjecture for cases k > 5 and k < 3. The proof itself indicates
a somewhat suprising connection between two seemingly unrelated graph
classes - the string graphs (that correspond to the unbounded case) and
the induced subgraphs of the extended grid (which correspond to the case
k=1). The cases k = 3, 4, 5 remain open.

The talk is based on a joint paper with Michael Coury, Pavol Hell, and Jan
Kratochvil.

Slides: Faithful Representations of Graphs by Islands
in the Extended Grid