# zbMATH — the first resource for mathematics

Spanning 2-connected subgraphs in alphabet graphs, special classes of grid graphs. (English) Zbl 1053.05093
A grid graph is a graph isomorphic to an induced subgraph of an $$s\times t$$-grid for some positive integers $$s, t$$. For each letter $$\lambda\in\{a, b, \ldots, z\}$$ and each integer $$n\geq 3$$, the authors define an induced subgraph $$\Lambda_n$$ of the $$(3n-2)\times(5n-4)$$-grid that represents the letter $$\lambda$$ in a natural way. Then, a graph is called an alphabet graph if it is isomorphic to $$\Lambda_n$$ for some letter $$\lambda$$ and some integer $$n\geq 3$$. Thus, alphabet graphs are special grid graphs.
The authors characterize all Hamiltonian alphabet graphs and solve the problem of determining a spanning 2-connected subgraph with minimum number of edges in alphabet graphs. Note that in general grid graphs, the above problems are NP-hard [A. Itai, C. H. Papadimitriou and J. L. Szwarcfiter, SIAM J. Comput. 11, 676–686 (1982; Zbl 0506.05043)].

##### MSC:
 05C62 Graph representations (geometric and intersection representations, etc.) 68R10 Graph theory (including graph drawing) in computer science 05C45 Eulerian and Hamiltonian graphs