Computational topology of graphs on surfaces

Computational topology is an area that revisits topological problems from an algorithmic point of view, and develops topological tools for improved algorithms. We survey results in computational topology that are concerned with graphs drawn on surfaces. Typical questions include representing surfaces and graphs embedded on them computationally, deciding whether a graph embeds on a surface, solving computational problems related to homotopy, optimizing curves and graphs on surfaces, and solving standard graph algorithm problems more efficiently in the case of surface-embedded graphs.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-02-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1201/9781315119601-23arXiv 1702.05358
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximating connectivity domination in weighted bounded-genus graphs

  2016cited by this paper
• Shortest Path Embeddings of Graphs on Surfaces

  2016cited by this paper
• Minimum cycle and homology bases of surface-embedded graphs

  2016cited by this paper
• A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

  2016cited by this paper
• Untangling Planar Curves

  2016cited by this paper
• A Practical Method for the Minimum Genus of a Graph: Models and Experiments

  2016cited by this paper
• A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface

  2015cited by this paper
• Bidimensionality and Parameterized Algorithms (Invited Talk)

  2015cited by this paper
• Computing the Geometric Intersection Number of Curves

  2015cited by this paper
• Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals

  2015cited by this paper
• Crossing Number is Hard for Kernelization

  2015cited by this paper
• Embedding and canonizing graphs of bounded genus in logspace

  2014cited by this paper
• Arcs intersecting at most once

  2014influential reference
• 2-manifold Recognition Is in Logspace

  2014cited by this paper
• Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

  2014cited by this paper
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

  2014cited by this paper
• Beyond the Euler Characteristic: Approximating the Genus of General Graphs

  2014cited by this paper
• Computing the Stretch of an Embedded Graph

  2014cited by this paper
• Algorithms for embedded graphs

  2014cited by this paper
• The Graph Crossing Number and its Variants: A Survey

  2013cited by this paper
• Counting and Sampling Minimum Cuts in Genus $$g$$g Graphs

  2013cited by this paper
• String graphs and separators

  2013cited by this paper
• A Better Bound for the Pair-Crossing Number

  2013cited by this paper
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

  2013cited by this paper
• A primer on mapping class groups

  2013cited by this paper
• Untangling two systems of noncrossing curves

  2013cited by this paper
• Measuring similarity between curves on 2-manifolds via homotopy area

  2013cited by this paper
• Hanani-Tutte and Related Results

  2013cited by this paper
• Geometry : intuitive, discrete, and convex : a tribute to László Fejes Tóth

  2013cited by this paper
• Transforming Curves on Surfaces Redux

  2013cited by this paper
• A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

  2013cited by this paper
• Global Minimum Cuts in Surface-Embedded Graphs

  2012cited by this paper
• Improved Bounds for Bipartite Matching on Surfaces

  2012influential reference
• Hardness of Approximation for Crossing Number

  2012cited by this paper
• Multiple-Source Shortest Paths in Embedded Graphs

  2012cited by this paper
• Planarizing an Unknown Surface

  2012cited by this paper
• Graph Minors. XXII. Irrelevant vertices in linkage problems

  2012cited by this paper
• Graph Minors and Parameterized Algorithm Design

  2012cited by this paper
• Algorithms for the edge-width of an embedded graph

  2012influential reference
• Contraction checking in graphs on surfaces

  2012cited by this paper
• Combinatorial Optimization of Cycles and Bases

  2012cited by this paper
• How to Walk Your Dog in the Mountains with No Magic Leash

  2012cited by this paper
• Tracing Compressed Curves in Triangulated Surfaces

  2012influential reference
• Errors in graph embedding algorithms

  2011cited by this paper
• Shortest non-trivial cycles in directed surface graphs

  2011influential reference
• Computing replacement paths in surface embedded graphs

  2011cited by this paper
• A Primer on Mapping Class Groups (Pms-49)

  2011cited by this paper
• Shortest non-crossing walks in the plane

  2011cited by this paper
• Minimum cuts and shortest non-separating cycles via homology covers

  2011cited by this paper
• Improved algorithms for min cut and max flow in undirected planar graphs

  2011cited by this paper
• Asymptotic enumeration of non-crossing partitions on surfaces

  2011cited by this paper
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

  2011cited by this paper
• On the Homotopy Test on Surfaces

  2011cited by this paper
• Finding Cycles with Topological Properties in Embedded Graphs

  2011cited by this paper
• Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

  2011cited by this paper
• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs

  2011cited by this paper
• Optimal Stochastic Planarization

  2010cited by this paper
• Computing the Shortest Essential Cycle

  2010cited by this paper
• An algorithm for the graph crossing number problem

  2010cited by this paper
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time

  2010cited by this paper
• Shortest Cut Graph of a Surface with Prescribed Vertex Set

  2010cited by this paper
• Approximating the crossing number of graphs embeddable in any orientable surface

  2010cited by this paper
• Dynamic programming for graphs on surfaces

  2010cited by this paper
• Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

  2010cited by this paper
• Adding one edge to planar graphs makes crossing number hard

  2010cited by this paper
• Finding shortest non-trivial cycles in directed graphs on surfaces

  2010cited by this paper
• The topology of scaling limits of positive genus random quadrangulations

  2010cited by this paper
• Maximum flows and parametric shortest paths in planar graphs

  2010cited by this paper
• Homology flows, cohomology cuts

  2009cited by this paper
• Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

  2009cited by this paper
• Tessellations of Random Maps of Arbitrary Genus

  2009cited by this paper
• Minimum cuts and shortest homologous cycles

  2009cited by this paper
• Strong Hanani--Tutte on the Projective Plane

  2009cited by this paper
• On the Height of a Homotopy

  2009cited by this paper
• Finding shortest contractible and shortest separating cycles in embedded graphs

  2009cited by this paper
• Planarity Testing

  2008cited by this paper
• Planar Graph Drawing

  2008cited by this paper
• Odd Crossing Number and Crossing Number Are Not the Same

  2008cited by this paper
• Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time

  2008cited by this paper
• A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width

  2008cited by this paper
• The Bidimensionality Theory and Its Algorithmic Applications

  2008cited by this paper
• Finding one tight cycle

  2008cited by this paper
• Computing crossing number in linear time

  2007cited by this paper
• Multiple source shortest paths in a genus g graph

  2007cited by this paper
• Some Recent Progress and Applications in Graph Minor Theory

  2007cited by this paper
• Removing even crossings on surfaces

  2007cited by this paper
• Approximation algorithms via contraction decomposition

  2007cited by this paper
• Splitting (complicated) surfaces is hard

  2006cited by this paper
• Tightening non-simple paths and cycles on surfaces

  2006cited by this paper
• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition

  2006cited by this paper
• Bidimensionality: new connections between FPT algorithms and PTASs

  2005cited by this paper
• Greedy optimal homotopy and homology generators

  2005cited by this paper
• Two maps with large representativity on one surface

  2005cited by this paper
• Algorithms for Graphs Embeddable with Few Crossings per Edge

  2005cited by this paper
• A linear-time approximation scheme for planar weighted TSP

  2005cited by this paper
• Recent advances in compression of 3D meshes

  2005cited by this paper
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

  2005cited by this paper
• Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

  2005cited by this paper
• Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs

  2005cited by this paper
• The Bidimensional Theory of Bounded-Genus Graphs

  2004cited by this paper

• Large induced forests in planar multigraphs

  2026cites this paper
• Disjoint Paths Problem with Group-Expressable Constraints

  2025cites this paper
• Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers

  2024cites this paper
• Computing shortest closed curves on non-orientable surfaces

  2024influential citation
• Mitochondrial networks through the lens of mathematics

  2023cites this paper
• An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number

  2023cites this paper
• On Computing Homological Hitting Sets

  2023cites this paper
• Spiraling and Folding: The Topological View

  2022cites this paper
• Short Topological Decompositions of Non-orientable Surfaces

  2022cites this paper
• An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes

  2021cites this paper
• Approximating Maximum Integral Multiflows on Bounded Genus Graphs

  2020cites this paper
• A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs

  2019cites this paper
• Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

  2019cites this paper
• Finding a Shortest Non-Zero Path in Group-Labeled Graphs

  2019cites this paper
• Embedding graphs into two-dimensional simplicial complexes

  2018cites this paper
• Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs

  2018cites this paper
• The genus of generalized random and quasirandom graphs

  2018cites this paper
• Bundled Crossings Revisited

  2018cites this paper
• Embedding Half-Edge Graphs in Punctured Surfaces

  2017cites this paper
• A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals

  2016cites this paper
• Algorithms and combinatorics for geometric graphs

  2015influential citation
• Beyond-Planar Graphs: Models, Structures and Geometric Representations

  year unknowncites this paper