Beyond and beneath planarity

Jul 23, 2016

Sprecher:innen

Über

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.

Organisator

Kategorien

Über The Mathematics of Jiří Matoušek

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

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? The Mathematics of Jiří Matoušek folgen