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 (55)
- 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
- A Direct Proof of the Strong Hanani–Tutte Theorem on the Projective Plane
- Linkless and flat embeddings in 3-space
- Maximum Cut Parameterized by Crossing Number
- The Common Structure of the Curves Having a Same Gauss Word
- Title not available (Why is that?)
- 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
- The crossing number of a projective graph is quadratic in the face–width
- The Birth and Early Years of Parameterized Complexity
- A Basic Parameterized Complexity Primer
- Multicuts in planar and bounded-genus graphs with bounded number of terminals
- Graph Minors and Parameterized Algorithm Design
- Bundled Crossings Revisited
- Some recent progress and applications in graph minor theory
- 2-restricted extensions of partial embeddings of graphs
- Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
- Bundled crossings revisited
- Errors in graph embedding algorithms
- Deleting vertices to graphs of bounded genus
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- 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
- Minimal Disconnected Cuts in Planar Graphs
- 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
- A practical algorithm for the computation of the genus
- Properties of Large 2-Crossing-Critical Graphs
- Title not available (Why is that?)
- Graph minor theory
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Title not available (Why is that?)
- 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
- The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex
- Graphs whose complement and square are isomorphic
- Approximation Algorithms for Euler Genus and Related Problems
- Embedding of sign-regular signed graphs and its spectral analysis
- Dynamic programming for graphs on surfaces
- A more accurate view of the flat wall theorem
- Embeddings of \(k\)-complexes into \(2k\)-manifolds
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)
