| Autor: | Anastasios Sidiropoulos, Yury Makarychev, Amir Nayyeri |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Theory of Computing. 13:1-47 |
| ISSN: | 1557-2862 |
| Popis: | The genus of a graph is a very basic parameter in topological graph theory, that has been the subject of extensive study. Perhaps surprisingly, despite its importance, the problem of approximating the genus of a graph is very poorly understood. It has been shown to be NPcomplete by Thomassen [Tho89], and the best known upper bound for general graphs is an O(n)-approximation that follows by Euler’s characteristic. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|