# 20 Years of Negami’s Planar Cover Conjecture

@article{Hlinn201020YO, title={20 Years of Negami’s Planar Cover Conjecture}, author={Petr Hliněn{\'y}}, journal={Graphs and Combinatorics}, year={2010}, volume={26}, pages={525-536} }

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 over ten related research papers have been published during the past 20 years of investigation, this beautiful conjecture is still open in 2008. We give a short accessible survey on Negami’s conjecture and all the… Expand

#### 10 Citations

How Not to Characterize Planar-Emulable Graphs

- Mathematics, Computer Science
- IWOCA
- 2011

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)—a problem raised in Fellows' thesis (1985) and conceptually related… Expand

How not to characterize planar-emulable graphs

- Mathematics, Computer Science
- Adv. Appl. Math.
- 2013

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph)-a problem raised already in [email protected]? thesis (1985) and… Expand

And Fellows' Conjecture Yo'av Rieck and Yasushi Yamashita

- 2009

In 1988 Fellows conjectured that if a finite, connected grap h dmits a finite planar emulator, then it admits a finite planar cover. We cons truct a finite planar emulator for K4,5−4K2. D. Archdeacon… Expand

Planar emulators conjecture is nearly true for cubic graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 2015

We prove that a cubic nonprojective graph cannot have a finite planar emulator unless it belongs to one of two very special cases (in which the answer is open). This shows that Fellows' planar… Expand

Minor-minimal non-projective planar graphs with an internal 3-separation

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2011

It is proved that a graph is projective planar if and only if it has no minor isomorphic to a graph from a list of 35 specific graphs. Expand

Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs

- Mathematics
- 2019

To every linear binary-constraint system (LinBCS) non-local game, there is an associated algebraic object called the solution group. Cleve, Liu, and Slofstra showed that a LinBCS game has a perfect… Expand

Decidability of regular language genus computation

- Computer Science, Mathematics
- Mathematical Structures in Computer Science
- 2019

It is shown that a new family of regular languages on a two-letter alphabet having arbitrary high genus and the genus size can grow at least exponentially in size |L|, which implies that the planarity of a regular language is decidable. Expand

Mike Fellows: Weaving the Web of Mathematics and Adventure

- Computer Science, Mathematics
- The Multivariate Algorithmic Revolution and Beyond
- 2012

This informal tribute in honor of Mike Fellows' 60th birthday is based on some personal recollections.

A Guide to the Discharging Method

- Mathematics
- 2013

We provide a “how-to” guide to the use and application of the Discharging Method. Our aim is not to exhaustively survey results that have been proved by this technique, but rather to demystify the… Expand

Finite planar emulators for K4, 5-4K2 and K1, 2, 2, 2 and Fellows' Conjecture

- Mathematics, Computer Science
- Eur. J. Comb.
- 2010

A finite planar emulator is constructed for K"4","5-4K"2", which provides a counterexample to Fellows' Conjecture and proves that Negami's Planar Cover Conjectured is true if and only if K"1","2","2,''2 admits no finitePlanar cover. Expand

#### References

SHOWING 1-10 OF 38 REFERENCES

A note on possible extensions of Negami's conjecture

- Computer Science
- J. Graph Theory
- 1999

This paper suggests another formulation of Negami's conjecture that has a straightforward generalization to higher nonorientable surfaces, and provides some support for the generalized version of this conjecture. Expand

A note on possible extensions of Negami's conjecture

- Mathematics
- 1999

A graph H is a cover of a graph G, if there exists a mapping φ from V(H) onto V(G) such that for every vertex ν of G, φ maps the neighbors of ν in H bijectively onto the neighbors of φ(ν) in G.… Expand

On possible counterexamples to Negami's planar cover conjecture

- Mathematics, Computer Science
- J. Graph Theory
- 2004

It is shown that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture, and a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in the list. Expand

On possible counterexamples to Negami's planar cover conjecture

- Mathematics
- 2004

A simple graph H is a cover of a graph G if there exists a mapping Φ from H onto G such that Φ maps the neighbors of every vertex u in H bijectively to the neighbors of Φ (ν) in G. Negami conjectured… Expand

K4, 4 - e has no finite planar cover

- Computer Science
- J. Graph Theory
- 1998

It is proved the non-existence of a finite planar cover of K4,4−e, which is a graph that has an embedding in the projective plane and no minor-minimal non-projective graph has a finitePlanar cover. Expand

Another two graphs with no planar covers

- Mathematics
- 2001

A graph H is a cover of a graph G if there exists a mapping Φ from V(H) onto V(G) such that Φ maps the neighbors of every vertex ν in H bijectively to the neighbors of Φ(ν) in G. Negami conjectured… Expand

A Kuratowski theorem for the projective plane

- Mathematics, Computer Science
- J. Graph Theory
- 1981

Let I ( S ) denote the set of graphs, each with no valency 2 vertices, which are irreducible for S, and using this notation the authors state Kuratowski's theorem. Expand

On the parity of planar covers

- Mathematics, Computer Science
- J. Graph Theory
- 1990

It is proved that if G is a planar graph that covers a nonplanar H, then the fold number must be even. Expand

Composite planar coverings of graphs

- Computer Science, Mathematics
- Discret. Math.
- 2003

We shall prove that a connected graph G is projective-planar if and only if it has a 2n-fold planar connected covering obtained as a composition of an n-fold covering and a double covering for some… Expand

The spherical genus and virtually planar graphs

- Mathematics, Computer Science
- Discret. Math.
- 1988

It is shown that G is virtually planar if and only if G is either planar or projective-planar and that sph( G ) = 1, 2 or ∞. Expand