论文标题
线性时间中地图的自动形态组
Automorphism groups of maps in linear time
论文作者
论文摘要
通过地图，我们的意思是封闭的紧凑型表面的$ 2 $细胞分解，即，图形的嵌入，使每个脸部都同构对开放盘。地图的自动形态可以被认为是在嵌入中保留顶点 - 边缘事件的顶点的排列。当下面的表面是可定向的时，地图的每个自动形态都决定表面具有角度的同态。虽然猜想没有用于测试不受约束属的映射同构的“真正的次级”算法，但我们提出了一种线性时间算法，用于计算由底层表面的属的自动形态群的生成器。该算法应用了一系列局部减少的序列，并产生均匀的图，同时保留了自动形态组。原始地图的自动形态组可以从线性时间的统一地图的自动形态组中重建。我们还通过利用抗双歧杆双覆盖的方式将算法扩展到不可方向的表面。
By a map we mean a $2$-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.
