21 years of Negami's planar cover conjecture

HLINĚNÝ, Petr. 21 years of Negami's planar cover conjecture. In Workshop on Graph Covers (ATCAGC 2009), Finse, Norsko. 2009.

Základní údaje

• Originální název: 21 years of Negami's planar cover conjecture
• Název česky: 21 let Negamiho hypotézy planárních pokrytí
• Autoři: HLINĚNÝ, Petr.
• Vydání: Workshop on Graph Covers (ATCAGC 2009), Finse, Norsko, 2009.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Vyžádané přednášky
• Obor: 10101 Pure mathematics
• Stát vydavatele: Norsko
• Utajení: není předmětem státního či obchodního tajemství
• Organizační jednotka: Fakulta informatiky
• Klíčová slova anglicky: planar covers; projective embedding
• Příznaky: Mezinárodní význam

Anotace

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.

Anotace česky

Ve článku shrnujeme všechny doposud dosažené výsledky při řešení hypotézy planárních pokrytí, kterou zformuloval Negami v roce 1988.

Návaznosti

• GA201/08/0308, projekt VaV: Název: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti

Investor: Grantová agentura ČR, Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy