×

Faithful representations of graphs by islands in the extended grid. (English) Zbl 1283.68269

López-Ortiz, Alejandro (ed.), LATIN 2010: Theoretical informatics. 9th Latin American symposium, Oaxaca, Mexico, April 19–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12199-9/pbk). Lecture Notes in Computer Science 6034, 131-142 (2010).
Summary: We investigate embeddings of graphs into the infinite extended grid graph. The problem was motivated by computation on adiabatic quantum computers, but it is related to a number of other well studied grid embedding problems. Such problems typically deal with representing vertices by grid points, and edges by grid paths, while minimizing some objective function such as the area or the maximum length of the grid paths representing the edges. Our particular model, while expressible in this language, is more naturally viewed as one 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 < 3\) and \(k > 5\); the cases \(k = 3\), 4, 5 remain open.
For the entire collection see [Zbl 1185.68011].

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI