How Not to Characterize Planar-emulable Graphs
| Authors | |
|---|---|
| Year of publication | 2011 |
| Type | Article in Proceedings |
| Conference | COMBINATORIAL ALGORITHMS, Lecture Notes in Computer Science 7056 |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1007/978-3-642-25011-8_9 |
| Field | General mathematics |
| Keywords | projective graph; planar emulator; |
| Description | 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. |
| Related projects: |