Project information
Planar graph emulators
(PLAGE)
- Project Identification
- MUNI/C/0883/2010
- Project Period
- 1/2011 - 12/2011
- Investor / Pogramme / Project type
-
Masaryk University
- Grant Agency of Masaryk University
- Rector's Program
- MU Faculty or unit
-
Faculty of Informatics
- Mgr. et Mgr. Martin Derka, M.Sc.
Projekt se pohybuje v oblasti teorie grafů a zabývá se problémem existence konečných rovinných emulátorů pro neprojektivní grafy. Podle hypotézy M. Fellowse (1985) takové emulátory neexistují. Tato hypotéza byla ale na konci roku 2008 překvapivě vyvrácena. Po více než 20 letech se tedy toto pole se otevřelo pro nový výzkum. Řešitel projektu ve své bakalářské práci ukázal, že existuje pouze konečná množina důležitých neprojektivních grafů, které mají konečný rovinný emulátor a zároveň neobsahují ani jeden z 6 problematických minorů. Projekt navazuje na předchozí výzkum a klade si za cíl prohloubit a následně publikovat dosažené výsledky.