We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Hanani-Tutte for approximating maps of graphs

Formal Metadata

Title
Hanani-Tutte for approximating maps of graphs
Title of Series
Number of Parts
24
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.
Keywords