Author(s):

Fulek, Radoslav; Kynčl, Jan

Title: 
HananiTutte for approximating maps of graphs

Title Series: 
Leibniz International Proceedings in Information, LIPIcs

Affiliation 
IST Austria 
Abstract: 
We resolve in the affirmative conjectures of A. Skopenkov and Repovš (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.

Keywords: 
computational geometry; Graph theory; Computation theory; Planarity; Clustered planarity; HananiTutte theorem; Graph embeddings; Graph embedding; Map approximation; Weak embedding; Piecewise linear techniques

Conference Title:

SoCG: Symposium on Computational Geometry

Volume: 
99

Conference Dates:

June 11  14, 2018

Conference Location:

Budapest, Hungary

ISBN:

18688969 (ISSN); 9783959770668 (ISBN)

Publisher:

Schloss Dagstuhl  LeibnizZentrum für Informatik

Date Published:

20180101

Start Page: 
391

End Page:

3915

DOI: 
10.4230/LIPIcs.SoCG.2018.39

Open access: 
yes (repository) 