Combinatorics Seminar
Radoslav Fulek
Institute of Science and Technology Austria
Hanani--Tutte theorem for c-planarity with pipes
Abstract: We resolve in the affirmative a conjecture of 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 almost immediately implies that flat c-planarity can be tested in polynomial time if
a plane drawing of the cluster adjacency graph is given as a part of the input.
More precisely, an instance of this problem consists of (i) a planar graph $G$ whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region $R$ of the plane given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise non-intersecting ``pipes''
corresponding to the bundles, connecting certain pairs of these discs.
We are to decide whether $G$ can be embedded inside $R$ 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 Jan Kyncl.
Monday December 5, 2016 at 2:00 PM in SEO 612