Automorphisms and Isomorphisms of Maps in Linear Time

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F25%3A43974701" target="_blank" >RIV/49777513:23520/25:43974701 - isvavai.cz</a>

Výsledek na webu

<a href="https://dl.acm.org/doi/10.1145/3686798" target="_blank" >https://dl.acm.org/doi/10.1145/3686798</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3686798" target="_blank" >10.1145/3686798</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Automorphisms and Isomorphisms of Maps in Linear Time

Popis výsledku v původním jazyce

A map is 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. An automorphism of a map can be thought of as a permutation of the vertices, which preserves the vertex-edge-face incidences in the embedding. Every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no &quot;truly subquadratic&quot; 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 on an orientable surface of genus g not equal 0, parametrized by the genus g . A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex v does not depend on the choice of v . 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 associated uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. The algorithm can be used to solve the map isomorphism problem between maps (orientable or non-orientable) of bounded negative Euler characteristic.

Název v anglickém jazyce

Automorphisms and Isomorphisms of Maps in Linear Time

Popis výsledku anglicky

A map is 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. An automorphism of a map can be thought of as a permutation of the vertices, which preserves the vertex-edge-face incidences in the embedding. Every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no &quot;truly subquadratic&quot; 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 on an orientable surface of genus g not equal 0, parametrized by the genus g . A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex v does not depend on the choice of v . 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 associated uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. The algorithm can be used to solve the map isomorphism problem between maps (orientable or non-orientable) of bounded negative Euler characteristic.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Algorithms

ISSN

1549-6325

e-ISSN

1549-6333

Svazek periodika

21

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

32

Strana od-do

nestránkováno

Kód UT WoS článku

001399998600003

EID výsledku v databázi Scopus

—