Publication details
20 years of Negami's planar cover conjecture
| Basic information | |
|---|---|
| Original title: | 20 years of Negami's planar cover conjecture |
| Author: | Petr Hliněný |
| Further information | |
|---|---|
| Citation: | HLINĚNÝ, Petr. 20 years of Negami's planar cover conjecture. Graphs and Combinatorics, Tokyo, Springer Japan, Japan. ISSN 0911 -0119, 2010, vol. 26, no. 4, pp. 525-536. |
| Original language: | English |
| Field: | General mathematics |
| Type: | Article in Periodical |
| Keywords: | planar covers; projective embedding |
In 1988, Seiya Negami published a conjecture stating that a graph $G$ has a finite planar cover (i.e.~a homomorphism from some planar graph onto $G$ which maps the vertex neighbourhoods bijectively) if and only if $G$ embeds in the projective plane. Though the "if" direction is easy, and some supporting weaker statements have been shown by him, the conjecture is still open, after more than 20 years of intensive investigation. We review the (quite significant) progress made so far in solving Negami's conjecture, and propose possible promising directions of future research.
Related projects:
- Highly Parallel and Distributed Computing Systems
- Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity
