Beyond and beneath planarity

Jul 23, 2016

Speakers

About

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.

Organizer

Categories

About The Mathematics of Jiří Matoušek

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

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow The Mathematics of Jiří Matoušek