Detailed Information on Publication Record
2011
How Not to Characterize Planar-emulable Graphs
HLINĚNÝ, Petr, Martin DERKA, Markus CHIMANI and Matěj KLUSÁČEKBasic information
Original name
How Not to Characterize Planar-emulable Graphs
Name in Czech
Jak nepopsat grafy s planárními emulátory
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution), Martin DERKA (203 Czech Republic, belonging to the institution), Markus CHIMANI (40 Austria) and Matěj KLUSÁČEK (203 Czech Republic, belonging to the institution)
Edition
Německo, COMBINATORIAL ALGORITHMS, Lecture Notes in Computer Science 7056, p. 106-120, 15 pp. 2011
Publisher
Springer Verlag
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10101 Pure mathematics
Country of publisher
Canada
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
RIV identification code
RIV/00216224:14330/11:00050170
Organization unit
Faculty of Informatics
ISBN
978-3-642-25010-1
UT WoS
000308512000009
Keywords in English
projective graph; planar emulator;
Tags
International impact, Reviewed
Změněno: 4/2/2013 12:43, prof. RNDr. Petr Hliněný, Ph.D.
V originále
We investigate the question of which graphs have {\em planar emulators} (a locally-surjective homomorphism from some finite planar graph)---% a problem raised in Fellows' thesis (1985) and conceptually related to the better known planar cover conjecture by Negami (1986). For over two decades, the planar emulator problem lived poorly in a shadow of Negami's conjecture---which is still open---as the two were considered equivalent. But, in the end of 2008, a surprising construction by Rieck and Yamashita falsified the natural ``planar emulator conjecture'', and thus opened a whole new research field. We present further results and constructions which show how far the planar-emulability concept is from planar-coverability, and that the traditional idea of likening it to projective embeddability is actually very out-of-place. We also present several positive partial characterizations of planar-emulable graphs.
In Czech
Ukazujeme, jak vzdálené jsou grafy s rovinnými emulátory grafům s rovinným pokrytím.
Links
GEGIG/11/E023, research and development project |
| ||
MSM0021622419, plan (intention) |
| ||
MUNI/A/0914/2009, interní kód MU |
| ||
1M0545, research and development project |
|