Isomorphisms of maps on the sphere

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://www.ams.org/books/conm/764/" target="_blank" >http://www.ams.org/books/conm/764/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1090/conm/764/15358" target="_blank" >10.1090/conm/764/15358</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Isomorphisms of maps on the sphere

Popis výsledku v původním jazyce

For a class of objects with a well-defined isomorphism relation the isomorphism problem asks to determine the algorithmic complexity of the decision whether two given objects are, or are not, isomorphic. Theorems by Steinitz (1916), Whitney (1933) and Mani (1971) show that the isomorphism problems for convex polyhedra, for 3-connected planar graphs, and for the spherical maps are closely related. In 1974, Hopcroft and Wong investigated the complexity of the graph isomorphism problem for polyhedral graphs. They proved that the problem can be solved in linear time. We describe a modified linear-time algorithm solving the isomorphism problem for spherical maps based on the approach by Hopcroft and Wong. The paper includes a detailed description of the algorithm including proofs. Moreover, our modified algorithm allows to determine (in linear time) the group of orientation-preserving symmetries of a spherical map.

Název v anglickém jazyce

Isomorphisms of maps on the sphere

Popis výsledku anglicky

For a class of objects with a well-defined isomorphism relation the isomorphism problem asks to determine the algorithmic complexity of the decision whether two given objects are, or are not, isomorphic. Theorems by Steinitz (1916), Whitney (1933) and Mani (1971) show that the isomorphism problems for convex polyhedra, for 3-connected planar graphs, and for the spherical maps are closely related. In 1974, Hopcroft and Wong investigated the complexity of the graph isomorphism problem for polyhedral graphs. They proved that the problem can be solved in linear time. We describe a modified linear-time algorithm solving the isomorphism problem for spherical maps based on the approach by Hopcroft and Wong. The paper includes a detailed description of the algorithm including proofs. Moreover, our modified algorithm allows to determine (in linear time) the group of orientation-preserving symmetries of a spherical map.

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)

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)

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ů

Název statě ve sborníku

Polytopes and Discrete Geometry

ISBN

978-1-4704-4897-4

ISSN

0271-4132

e-ISSN

—

Počet stran výsledku

23

Strana od-do

125-147

Název nakladatele

American Mathematical Society

Místo vydání

Providence

Místo konání akce

Boston

Datum konání akce

21. 4. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—