×

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
PDF BibTeX XML Cite