Hanani-Tutte for approximating maps of graphs
From MaRDI portal
Publication:5115807
Abstract: We resolve in the affirmative conjectures of Repovs and A. Skopenkov (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 if 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 non-intersecting "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.
Recommendations
- Stability of intersections of graphs in the plane and the van Kampen obstruction
- Boolean approach to planar embeddings of a graph
- Clustered planarity testing revisited
- Advances on Testing C-Planarity of Embedded Flat Clustered Graphs
- scientific article; zbMATH DE number 3968607
- scientific article; zbMATH DE number 3961641
- Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters
- Toward a theory of planarity: Hanani-Tutte and planarity variants
- Toward a theory of planarity: Hanani-Tutte and planarity variants
- scientific article; zbMATH DE number 3914341
Cites work
- A deleted product criterion for approximability of maps by embeddings
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Beyond level planarity
- Clustered planarity testing revisited
- Clustered Planarity with Pipes
- Detecting weakly simple polygons
- Efficient Planarity Testing
- Embedding Graphs into Embedded Graphs
- Graphs on surfaces
- Hanani-Tutte and related results
- Hanani-Tutte for Radial Planarity
- Hanani-Tutte for Radial Planarity II
- Hanani-Tutte, monotone drawings, and level-planarity
- How to draw a planar clustered graph
- scientific article; zbMATH DE number 1974122 (Why is no real title available?)
- scientific article; zbMATH DE number 1498604 (Why is no real title available?)
- Multiplying matrices faster than coppersmith-winograd
- On approximability by embeddings of cycles in the plane.
- On embedding a cycle in a plane graph
- Planarity for clustered graphs
- Powers of tensors and fast matrix multiplication
- Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
- Recognizing weak embeddings of graphs
- Recognizing weakly simple polygons
- Removing even crossings
- Solving sparse linear equations over finite fields
- Strip planarity testing for embedded planar graphs
- The graph genus problem is NP-complete
- Toward a theory of crossing numbers
- Toward a theory of planarity: Hanani-Tutte and planarity variants
- Unified Hanani-Tutte theorem
- Über wesentlich unplättbare Kurven im dreidimensionalen Raume
Cited in
(20)- On approximability by embeddings of cycles in the plane.
- Clustered planarity = flat clustered planarity
- Stability of intersections of graphs in the plane and the van Kampen obstruction
- C-planarity testing of embedded clustered graphs with bounded dual carving-width
- Embedding graphs into embedded graphs
- Clustered planarity with pipes
- Hanani-Tutte for radial planarity. II
- Hanani-Tutte for Radial Planarity II
- A note about pruning and Hénon maps
- Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
- Alternating maps on Hatcher–Thurston graphs
- Beyond Clustered Planar Graphs
- Hanani--Tutte and Hierarchical Partial Planarity
- Atomic Embeddability, Clustered Planarity, and Thickenability
- scientific article; zbMATH DE number 7559239 (Why is no real title available?)
- Hanani-Tutte for Radial Planarity
- Hanani-Tutte for Radial Planarity
- Crossing minimization in perturbed drawings
- Crossing minimization in perturbed drawings
- Shelling and sinking graphs on the sphere
This page was built for publication: Hanani-Tutte for approximating maps of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115807)
