How Not to Characterize Planar-emulable Graphs

HLINĚNÝ, Petr; Martin DERKA; Markus CHIMANI a Matěj KLUSÁČEK. How Not to Characterize Planar-emulable Graphs. In Costas S. Iliopoulos and William F. Smyth. COMBINATORIAL ALGORITHMS, Lecture Notes in Computer Science 7056. Německo: Springer Verlag, 2011, s. 106-120. ISBN 978-3-642-25010-1. Dostupné z: https://doi.org/10.1007/978-3-642-25011-8_9.

Základní údaje

Originální název

How Not to Characterize Planar-emulable Graphs

Název česky

Jak nepopsat grafy s planárními emulátory

Autoři

HLINĚNÝ, Petr ORCID; Martin DERKA; Markus CHIMANI a Matěj KLUSÁČEK

Vydání

Německo, COMBINATORIAL ALGORITHMS, Lecture Notes in Computer Science 7056, od s. 106-120, 15 s. 2011

Nakladatel

Springer Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Kanada

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/11:00050170

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-25010-1

DOI

https://doi.org/10.1007/978-3-642-25011-8_9

UT WoS

000308512000009

Klíčová slova anglicky

projective graph; planar emulator;

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.

Česky

Ukazujeme, jak vzdálené jsou grafy s rovinnými emulátory grafům s rovinným pokrytím.

---

Návaznosti

GEGIG/11/E023, projekt VaV	Název: Kreslení grafů a jejich geometrické reprezentace (Akronym: GraDR) Investor: Grantová agentura ČR, Graph Drawings and Representations
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
MUNI/A/0914/2009, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky