A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
From MaRDI portal
Publication:4255804
DOI10.1137/S089548019529248XzbMATH Open0931.05025OpenAlexW2082687277MaRDI QIDQ4255804FDOQ4255804
Authors: Bojan Mohar 
Publication date: 27 June 1999
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s089548019529248x
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cited In (57)
- A more accurate view of the flat wall theorem
- Embeddings of \(k\)-complexes into \(2k\)-manifolds
- Six-Critical Graphs on the Klein Bottle
- Projective plan and Möbius band obstructions
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
- On the upward embedding on the torus
- 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
- Title not available (Why is that?)
- Embedding graphs into two-dimensional simplicial complexes
- Linear-Time Test for Small Face Covers in any Fixed Surface
- Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable
- Five-coloring graphs on the Klein bottle
- Approximating the Crossing Number of Toroidal Graphs
- Approximation algorithms for Euler genus and related problems
- The crossing number of a projective graph is quadratic in the face–width
- Multicuts in planar and bounded-genus graphs with bounded number of terminals
- Algorithmic graph embeddings
- Some recent progress and applications in graph minor theory
- 2-restricted extensions of partial embeddings of graphs
- Embedding graphs in the torus in linear time
- Bundled crossings revisited
- Errors in graph embedding algorithms
- Deleting vertices to graphs of bounded genus
- Maximum cut parameterized by crossing number
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- 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
- Title not available (Why is that?)
- Stronger ILPs for the Graph Genus Problem.
- Approximation algorithms via contraction decomposition
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
- A fast algorithm for the product structure of planar graphs
- The parameterized complexity of finding a 2-sphere in a simplicial complex
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- 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
- Title not available (Why is that?)
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- 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
- Dynamic programming for graphs on surfaces
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)
