Fulek, Radoslav ;
Kyncl, Jan
HananiTutte for Approximating Maps of Graphs
Abstract
We resolve in the affirmative conjectures of A. Skopenkov and Repovs (1998), and M. Skopenkov (2003) generalizing the classical HananiTutte theorem to the setting of approximating maps of graphs on 2dimensional 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 intercluster edges are partitioned into bundles, and (ii) a region R of a 2dimensional 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.
BibTeX  Entry
@InProceedings{fulek_et_al:LIPIcs:2018:8752,
author = {Radoslav Fulek and Jan Kyncl},
title = {{HananiTutte for Approximating Maps of Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {39:139:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8752},
URN = {urn:nbn:de:0030drops87527},
doi = {10.4230/LIPIcs.SoCG.2018.39},
annote = {Keywords: HananiTutte theorem, graph embedding, map approximation, weak embedding, clustered planarity}
}
08.06.2018
Keywords: 

HananiTutte theorem, graph embedding, map approximation, weak embedding, clustered planarity 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

08.06.2018 