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