A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
From MaRDI portal
Recommendations
Cited in
(66)- On the upward embedding on the torus
- Projective plan and Möbius band obstructions
- Algorithmic graph embeddings
- 2-restricted extensions of partial embeddings of graphs
- Approximation algorithms via contraction decomposition
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Bundled crossings revisited
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- Toroidal grid minors and stretch in embedded graphs
- Deleting vertices to graphs of bounded genus
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Graphs whose complement and square are isomorphic
- A fast algorithm for the product structure of planar graphs
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
- Elimination of local bridges
- The birth and early years of parameterized complexity
- A basic parameterized complexity primer
- Graph minors and parameterized algorithm design
- Minimal disconnected cuts in planar graphs
- Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
- A direct proof of the strong Hanani-Tutte theorem on the projective plane
- scientific article; zbMATH DE number 7228873 (Why is no real title available?)
- Graph minor theory
- scientific article; zbMATH DE number 4142064 (Why is no real title available?)
- Linear-Time Test for Small Face Covers in any Fixed Surface
- The crossing number of a projective graph is quadratic in the face–width
- Linkless and flat embeddings in 3-space
- scientific article; zbMATH DE number 1256757 (Why is no real title available?)
- Approximation algorithms for Euler genus and related problems
- scientific article; zbMATH DE number 3995712 (Why is no real title available?)
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- The common structure of the curves having a same Gauss word
- Counting problems in parameterized complexity
- A practical algorithm for the computation of the genus
- Stronger ILPs for the Graph Genus Problem.
- Embedding of sign-regular signed graphs and its spectral analysis
- Properties of large 2-crossing-critical graphs
- Embedding graphs in the torus in linear time
- Embedding graphs into two-dimensional simplicial complexes
- Hanani-Tutte for approximating maps of graphs
- Maximum cut parameterized by crossing number
- Bundled crossings revisited
- New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- The parameterized complexity of finding a 2-sphere in a simplicial complex
- Six-Critical Graphs on the Klein Bottle
- Approximating the Crossing Number of Toroidal Graphs
- scientific article; zbMATH DE number 2192203 (Why is no real title available?)
- Dynamic programming for graphs on surfaces
- scientific article; zbMATH DE number 7662167 (Why is no real title available?)
- Algorithmic graph embeddings
- Embeddings of k-complexes into 2k-manifolds
- Errors in graph embedding algorithms
- A more accurate view of the flat wall theorem
- Immersions of bipartite graphs and numismatics
- Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
- Packing cycles in planar and bounded-genus graphs
- Efficient polynomial-time approximation scheme for the genus of dense graphs
- Five-coloring graphs on the Klein bottle
- An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
- Twin-width of graphs on surfaces
- Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
- An efficient genus algorithm based on graph rotations
- Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable
- Some recent progress and applications in graph minor theory
This page was built for publication: A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4255804)
