- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Hanani-Tutte for approximating maps of graphs
Open Collections
BIRS Workshop Lecture Videos
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 Metadata
Title |
Hanani-Tutte for approximating maps of graphs
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2017-08-22T15:20
|
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.
|
Extent |
25 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: IST Austria
|
Series | |
Date Available |
2018-04-10
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0365303
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International