J 2013

How Not to Characterize Planar-emulable Graphs

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

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 (203 Česká republika, garant, domácí), Martin DERKA (203 Česká republika, domácí), Markus CHIMANI (40 Rakousko) a Matěj KLUSÁČEK (203 Česká republika, domácí)

Vydání

Advances in Applied Mathematics, Holandsko, Elsevier, 2013, 0196-8858

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Nizozemské království

Utajení

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

Impakt faktor

Impact factor: 0.878

Kód RIV

RIV/00216224:14330/13:00065950

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000312573600004

Klíčová slova česky

projektivní graf; rovinný emulátor; minor grafu

Klíčová slova anglicky

Projective-planar graph; Planar emulator; Planar cover; Graph minor

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 21. 11. 2013 17:39, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

V originále

We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph) - a problem raised already 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 Negamis conjecture - which is still open - as the two were considered equivalent. But, at 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
MUNI/A/0760/2012, interní kód MU
Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)
Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty