| Title: | Isomorphisms of maps on the sphere |
| Other Titles: | Isomorfizmy máp na sféře |
| Authors: | Kawarabayashi, Ken-ichi Klavík, Pavel Mohar, Bojan Nedela, Roman Zeman, Peter |
| Citation: | KAWARABAYASHI, K., KLAVÍK, P., MOHAR, B., NEDELA, R., ZEMAN, P. Isomorphisms of maps on the sphere. In: Polytopes and Discrete Geometry. Providence: American Mathematical Society, 2021. s. 125-147. ISBN 978-1-4704-4897-4, ISSN 0271-4132. |
| Issue Date: | 2021 |
| Publisher: | American Mathematical Society |
| Document type: | konferenční příspěvek conferenceObject |
| URI: | http://hdl.handle.net/11025/43672 |
| ISBN: | 978-1-4704-4897-4 |
| ISSN: | 0271-4132 |
| Keywords: | Mapa grupa plocha algoritmus isomorfismus |
| Keywords in different language: | Map group surface algorithm isomorphism |
| Abstract: | Hopcroft a Wong v roku 1974 navrhli lineárny algoritmus na zjišťování isomorfismu polyherálních grafů. V příspěvku navrhneme modifikovaný algoritmus na řešení tohoto problému s lineárnou složitostí. Práce obsahuje detaily nevyhnutné pro implementaci i důkaz linearity. |
| Abstract in different language: | 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. |
| Rights: | Plný text je přístupný v rámci univerzity přihlášeným uživatelům. © American Mathematical Society |
| Appears in Collections: | Konferenční příspěvky / Conference Papers (KMA) Konferenční příspěvky / Conference papers (NTIS) OBD |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| conm15358.pdf | 307,76 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/43672Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.