A grid graph $G$ is a finite induced subgraph of the infinite 2-dimensional grid defined by $Z imes Z$ and all edges between pairs of vertices from $Z imes Z$ at Euclidean distance precisely 1. A natural drawing of $G$ is obtained by drawing its vertices in $mathbb{R}^2$ according to their coordinates. Apart from the outer face, all (inner) faces with area exceeding one (not bounded by a 4-cycle) in a natural drawing of $G$ are called the holes of $G$. We define 26 classes of grid graphs called alphabet graphs, with no or a few holes. We determine which of the alphabet graphs contain a Hamilton cycle, i.e. a cycle containing all vertices, and solve the problem of determining a spanning 2-connected subgraph with as few edges as possible for all alphabet graphs.
展开▼
机译：网格图$ G $是无限二维网格的有限归纳子图，它由$ Z x Z $以及精确地在1欧几里得距离处的$ Z xZ $顶点对之间的所有边定义。通过根据其坐标在$ mathbb {R} ^ 2 $中绘制其顶点来获得$ G $。除了外面之外，在$ G $的自然图形中面积超过一个（不受4个循环限制）的所有（内部）面都称为$ G $的孔。我们定义了26个称为字母图的网格图类，它们没有孔或只有几个孔。我们确定哪个字母图包含汉密尔顿循环（即包含所有顶点的循环），并解决为所有字母图确定跨度为2的连接子图且边缘尽可能少的问题。
展开▼
