We are interested in finding combinatorial criteria for embedding graphs into torus and using them in the embedding check algorithm. It is a well-known fact that any connected graph can be reduced to a one-vertex graph with loops and is homotopy equivalent to such a graph. If a connected graph has intersection of some edges, then some loops of one-vertex graph will also intersect. Therefore the problem of embedding graphs into some surface is equivalent to the question of embedding one-vertex graph in given surface. This paper considers a graph with rotations or rotation system called hieroglyph. The equivalence of four conditions is proved: (1) embedding hieroglyph into torus; (2) the absence of forbidden subgraphs in a hieroglyph; (3) some condition for the graph of loops; (4) the existence of a reduction of hieroglyph to one of the list of hieroglyphs. We also prove the existence of an algorithm with complexity $O(n)$ that recognizes embedding hieroglyph into torus.
翻译:我们有兴趣找到将图形嵌入横纹体并用于嵌入检查算法的组合标准。 众所周知, 任何连接的图形都可以压缩为带环的一面形图, 并且具有等同该图形的同质性。 如果连接的图形具有某些边缘的交叉点, 那么一些一面形图的循环也会相互交错。 因此, 将图形嵌入某些表面的问题相当于将一面图嵌入给定表面的问题。 本文考虑一个带有旋转或旋转系统的图表, 叫做象形体。 四个条件的等值已被证明:(1) 将象形形体嵌入图中;(2) 象形形图中缺少被禁止的子图;(3) 圆形图中的某些条件;(4) 将象形体缩小到象形体列表中的一个。 我们还证明存在一个复杂度为$( n)美元的算法, 承认将象形体嵌入象形体到象形体中。