Publication at Faculty of Mathematics and Physics |
2010
Abstract
We investigate embeddings of graphs into the infinite extended grid graph, where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid.
The connection is established by limiting the size (number of vertices) k of the representing islands. We study the problem of representability of an input graph G by islands of size at most k.
We conjecture that this problem is NP-complete for any positive integer k, and prove the conjecture for k 5; the cases k = 3, 4, 5 remain open.