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