Beyond and beneath planarity

23. Červenec 2016

Řečníci

O prezentaci

Topological graph is a graph with added information which pairs of edges are allowed to cross in a drawing in the plane. The AT graphs is realizable if such a drawing indeed exists. Unlike planarity, testing realizability of AT graphs is known to be computationally hard. In our paper with Jirka Matousek published in 1991 we exhibited an unexpected feature of this problem by showing that there exist realizable AT graphs that require exponential number of edge crossing in any realization. The construction naturally popped out in an at first sight much simpler problem of noncrossing drawings of graphs with specified regions for drawings of the edges that we conisdered with Torsten Ueckerdt in 2013.

Organizátor

Kategorie

O organizátorovi (The Mathematics of Jiří Matoušek )

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Uložení prezentace

Měla by být tato prezentace uložena po dobu 1000 let?

Jak ukládáme prezentace

Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %

Sdílení

Doporučená videa

Prezentace na podobné téma, kategorii nebo přednášejícího

Zajímají Vás podobná videa? Sledujte The Mathematics of Jiří Matoušek