A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
From MaRDI portal
Publication:4255804
DOI10.1137/S089548019529248XzbMath0931.05025OpenAlexW2082687277MaRDI QIDQ4255804
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
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A practical algorithm for the computation of the genus, Unnamed Item, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, Unnamed Item, Unnamed Item, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Graph Minors and Parameterized Algorithm Design, Six-Critical Graphs on the Klein Bottle, Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable, Embedding of sign-regular signed graphs and its spectral analysis, Properties of Large 2-Crossing-Critical Graphs, A fast algorithm for the product structure of planar graphs, Some recent progress and applications in graph minor theory, Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm, Multicuts in planar and bounded-genus graphs with bounded number of terminals, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Approximation Algorithms for Euler Genus and Related Problems, Projective plan and Möbius band obstructions, Minimal Disconnected Cuts in Planar Graphs, The crossing number of a projective graph is quadratic in the face–width, Linkless and flat embeddings in 3-space, Local search is a PTAS for feedback vertex set in minor-free graphs, A Direct Proof of the Strong Hanani–Tutte Theorem on the Projective Plane, Approximation algorithms via contraction decomposition, Errors in graph embedding algorithms, Embeddings of \(k\)-complexes into \(2k\)-manifolds, Unnamed Item, Unnamed Item, Maximum Cut Parameterized by Crossing Number, Bundled crossings revisited, A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number, Graphs whose complement and square are isomorphic, Approximating the Crossing Number of Toroidal Graphs, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Bundled Crossings Revisited, 2-restricted extensions of partial embeddings of graphs, Five-coloring graphs on the Klein bottle, Hanani-Tutte for approximating maps of graphs, Toroidal grid minors and stretch in embedded graphs, Graph minor theory, Stronger ILPs for the Graph Genus Problem., On the upward embedding on the torus, Unnamed Item, New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces, The Common Structure of the Curves Having a Same Gauss Word, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Deleting vertices to graphs of bounded genus, The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex, Dynamic programming for graphs on surfaces
