Automorphisms and Isomorphisms of Maps in Linear Time

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F21%3A43962831" target="_blank" >RIV/49777513:23520/21:43962831 - isvavai.cz</a>

Result on the web

<a href="https://drops.dagstuhl.de/opus/volltexte/2021/14068/pdf/lipics-vol198-icalp2021-complete.pdf" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2021/14068/pdf/lipics-vol198-icalp2021-complete.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2021.86" target="_blank" >10.4230/LIPIcs.ICALP.2021.86</a>

Result language

angličtina

Original language name

Automorphisms and Isomorphisms of Maps in Linear Time

Original language description

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. 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA20-15576S" target="_blank" >GA20-15576S: Graph Covers: Symmetries and Complexity</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2021

Confidentiality

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

Article name in the collection

48th International Colloquium on Automata, Languages, and Programming

ISBN

978-3-95977-195-5

ISSN

1868-8969

e-ISSN

—

Number of pages

15

Pages from-to

"86:1"-"86:15"

Publisher name

Dagstuhl Publishing

Place of publication

Saarbrücken/Wadern

Event location

Glasgow

Event date

Jul 12, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—