Faithful Representations of Graphs by Islands in the Extended Grid

Tomáš Vyskočil

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