---
res:
bibo_abstract:
- We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and
M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting
of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof
of this result is constructive and almost immediately implies an efficient algorithm
for testing whether a given piecewise linear map of a graph in a surface is approximable
by an embedding. More precisely, an instance of this 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 region R of a 2-dimensional compact surface
M given as the union of a set of pairwise disjoint discs corresponding to the
clusters and a set of pairwise disjoint "pipes" corresponding to the
bundles, connecting certain pairs of these discs. We are to decide whether G can
be embedded inside M 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Radoslav
foaf_name: Fulek, Radoslav
foaf_surname: Fulek
foaf_workInfoHomepage: http://www.librecat.org/personId=39F3FFE4-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0001-8485-1774
- foaf_Person:
foaf_givenName: Jan
foaf_name: Kynčl, Jan
foaf_surname: Kynčl
bibo_doi: 10.4230/LIPIcs.SoCG.2018.39
bibo_volume: 99
dct_date: 2018^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-3-95977-066-8
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Hanani-Tutte for approximating maps of graphs@
...