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

Formale Metadaten

Titel
Hanani-Tutte for approximating maps of graphs
Serientitel
Anzahl der Teile
24
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.
Schlagwörter