---
_id: '185'
abstract:
- lang: eng
  text: 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.
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
article_number: '39'
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: Jan
  full_name: Kynčl, Jan
  last_name: Kynčl
citation:
  ama: 'Fulek R, Kynčl J. Hanani-Tutte for approximating maps of graphs. In: Vol 99.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.39">10.4230/LIPIcs.SoCG.2018.39</a>'
  apa: 'Fulek, R., &#38; Kynčl, J. (2018). Hanani-Tutte for approximating maps of
    graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
    Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.39">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>'
  chicago: Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of
    Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a
    href="https://doi.org/10.4230/LIPIcs.SoCG.2018.39">https://doi.org/10.4230/LIPIcs.SoCG.2018.39</a>.
  ieee: 'R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented
    at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol.
    99.'
  ista: 'Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG:
    Symposium on Computational Geometry, Leibniz International Proceedings in Information,
    LIPIcs, vol. 99, 39.'
  mla: Fulek, Radoslav, and Jan Kynčl. <i>Hanani-Tutte for Approximating Maps of Graphs</i>.
    Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.39">10.4230/LIPIcs.SoCG.2018.39</a>.
  short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2018.
conference:
  end_date: 2018-06-14
  location: Budapest, Hungary
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2018-06-11
date_created: 2018-12-11T11:45:04Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:36Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.39
file:
- access_level: open_access
  checksum: f1b94f1a75b37c414a1f61d59fb2cd4c
  content_type: application/pdf
  creator: dernst
  date_created: 2018-12-17T12:33:52Z
  date_updated: 2020-07-14T12:45:19Z
  file_id: '5701'
  file_name: 2018_LIPIcs_Fulek.pdf
  file_size: 718857
  relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: '        99'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02281
  name: Eliminating intersections in drawings of graphs
publication_identifier:
  isbn:
  - 978-3-95977-066-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7735'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hanani-Tutte for approximating maps of graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...