BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Hanani-Tutte for approximating maps of graphs Fulek, Radoslav

Description

We resolve in the affirmative conjectures of A. Skopenkov and Repovs (1998), and M. Skopenkov (2003) generalizing the classical Hanani--Tutte theorem to the setting of approximating maps of graphs in the plane by embeddings. Our proof of this result is constructive, and implies the existence of a polynomial-time algorithm for the following problem.  An instance of the problem consists of (i) a graph $G$ whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a 2-dimensional surface $S$ given as the union of a set of pairwise disjoint discs corresponding to the  clusters and a set of pairwise non-intersecting strips, ``pipes'', corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether $G$ can be embedded inside $S$ so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once. Joint work with J. Kyncl.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International