Automorphisms and Isomorphisms of Maps in Linear Time
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
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. 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.
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. 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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA20-15576S" target="_blank" >GA20-15576S: Nakrývání grafů: Symetrie a složitost</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2021
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
48th International Colloquium on Automata, Languages, and Programming
ISBN
978-3-95977-195-5
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
15
Strana od-do
"86:1"-"86:15"
Název nakladatele
Dagstuhl Publishing
Místo vydání
Saarbrücken/Wadern
Místo konání akce
Glasgow
Datum konání akce
12. 7. 2021
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—