A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface

No abstract is available for this paper.

• Publication year

  1999

• Venue

  SIAM Journal on Discrete Mathematics

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S089548019529248X
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elimination of local bridges

  1997cited by this paper
• Graph Minors .XIII. The Disjoint Paths Problem

  1995cited by this paper
• Obstructions for the Disk and the Cylinder Embedding Extension Problems

  1994cited by this paper
• Triangulating a Surface with a Prescribed Graph

  1993cited by this paper
• Projective Planarity in Linear Time

  1993cited by this paper
• Topics In Combinatorics and Graph Theory

  1992cited by this paper
• An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs

  1991cited by this paper
• Paths, Flows, and VLSI-Layout

  1990cited by this paper
• Graph minors. VIII. A kuratowski theorem for general surfaces

  1990influential reference
• The Complexity of the Graph Embedding Problem

  1990cited by this paper
• Classification and detection of obstructions to planarity

  1990cited by this paper
• The Graph Genus Problem is NP-Complete

  1989cited by this paper
• A Kuratowski theorem for nonorientable surfaces

  1989cited by this paper
• Finding a maximum-genus graph imbedding

  1988cited by this paper
• A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees

  1985cited by this paper
• Depth-First Search and Kuratowski Subgraphs

  1984cited by this paper
• A Depth-First-Search Characterization of Planarity

  1982cited by this paper
• A Kuratowski theorem for the projective plane

  1981cited by this paper
• Embedding Graphs in the Plane—Algorithmic Aspects

  1980cited by this paper
• On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)

  1979cited by this paper
• 103 Graphs that are irreducible for the projective plane

  1979cited by this paper
• Blocks and the nonorientable genus of graphs

  1977cited by this paper
• Graph Theory with Applications

  1977cited by this paper
• The combinatorial map color theorem

  1977cited by this paper
• Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms

  1976cited by this paper
• Efficient Planarity Testing

  1974cited by this paper
• Dividing a Graph into Triconnected Components

  1973cited by this paper
• Time-bounded random access machines

  1972cited by this paper
• Additivity of the genus of a graph

  1962cited by this paper

• Catching Rats in H-minor-free Graphs

  2026cites this paper
• A High-Dimensional Extension of Wagner's Theorem and the Geometrization of Hypergraphs

  2025cites this paper
• Catching Rats in $H$-minor-free Graphs

  2025cites this paper
• Minor Containment and Disjoint Paths in Almost-Linear Time

  2024cites this paper
• An Efficient Genus Algorithm Based on Graph Rotations

  2024cites this paper
• On high genus extensions of Negami's conjecture

  2024cites this paper
• Bounding the Chromatic Number via High Dimensional Embedding

  2024cites this paper
• Genus of Embedded Graphs in Orientable Closed Surfaces

  2023cites this paper
• Twin-width of graphs on surfaces

  2023cites this paper
• Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern

  2023cites this paper
• Untangling Graphs on Surfaces

  2023cites this paper
• The Complexity of Chromatic Number When Restricted to graphs with Bounded Genus or Bounded Crossing Number

  2022influential citation
• Graph minors, decompositions and algorithms

  2022cites this paper
• Global Consistent Point Cloud Registration Based on Lie-algebraic Cohomology

  2022cites this paper
• Graph Theory – A Survey on the Occasion of the Abel Prize for László Lovász

  2022cites this paper
• Packing cycles in planar and bounded-genus graphs

  2022influential citation
• Counting Hamiltonian Cycles in 2-Tiled Graphs

  2021cites this paper
• A more accurate view of the Flat Wall Theorem

  2021cites this paper
• An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes

  2021influential citation
• Properties of Large 2-Crossing-Critical Graphs

  2021cites this paper
• A Fast Algorithm for the Product Structure of Planar Graphs

  2020cites this paper
• A Whitney Type Theorem for Surfaces: Characterising Graphs with Locally Planar Embeddings

  2020cites this paper
• Embedding of sign-regular signed graphs and its spectral analysis

  2020cites this paper
• A Practical Algorithm for the Computation of the Genus

  2020cites this paper
• Finding irrelevant vertices in linear time on bounded-genus graphs

  2019cites this paper
• New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces

  2019cites this paper
• Improved bounds for centered colorings

  2019cites this paper
• Polylogarithmic approximation for Euler genus on bounded degree graphs

  2019cites this paper
• Maximum Cut Parameterized by Crossing Number

  2019cites this paper
• A Polynomial-Time Algorithm to Compute Turaev–Viro Invariants TV 4 , q of 3-Manifolds with Bounded First Betti Number

  2019cites this paper
• Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

  2019influential citation
• Planar Graphs have Bounded Queue-Number

  2019cites this paper
• Impact of Symmetries in Graph Clustering

  2019cites this paper
• Stronger ILPs for the Graph Genus Problem

  2019cites this paper
• A Simple Local Search Gives a PTAS for the Feedback Vertex Set Problem in Minor-Free Graphs

  2019cites this paper
• Embeddings of k-Complexes into 2k-Manifolds

  2019cites this paper
• Embedding graphs into two-dimensional simplicial complexes

  2018influential citation
• The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex

  2018cites this paper
• Counting Problems in Parameterized Complexity

  2018cites this paper
• Two Results in Drawing Graphs on Surfaces

  2018cites this paper
• Bundled Crossings Revisited

  2018cites this paper
• Metric and analytic methods

  2018cites this paper
• Embedding of signed regular graphs

  2018cites this paper
• The genus of generalized random and quasirandom graphs

  2018influential citation
• Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs

  2018influential citation
• Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs

  2018cites this paper
• Surfaces and embedded graphs

  2017cites this paper
• Recognizing Weak Embeddings of Graphs

  2017cites this paper
• Deleting Vertices to Graphs of Bounded Genus

  2017cites this paper
• Computational topology of graphs on surfaces

  2017cites this paper
• Hanani-Tutte for approximating maps of graphs

  2017cites this paper
• Plane Permutations and their Applications to Graph Embeddings and Genome Rearrangements

  2017cites this paper
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory

  2017cites this paper
• Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

  2016cites this paper
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number

  2016cites this paper
• Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm

  2016cites this paper
• Scale-Dependent Variability and Quantitative Regimes in Graph-Theoretic Representations of Human Cortical Networks

  2016cites this paper
• A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

  2016cites this paper
• On the local genus distribution of graph embeddings

  2016cites this paper
• A Practical Algorithm for Embedding Graphs on Torus

  2015cites this paper
• Parameterized Algorithms

  2015cites this paper
• Why are certain polynomials hard?: A look at non-commutative, parameterized and homomorphism polynomials

  2015cites this paper
• Characterization of signed Gauss paragraphs

  2015cites this paper
• Graph Isomorphism for Bounded Genus Graphs In Linear Time

  2015influential citation
• The Common Structure of the Curves Having a Same Gauss Word

  2015cites this paper
• Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals

  2015cites this paper
• Minimal disconnected cuts in planar graphs

  2015cites this paper
• Pfaffian orientations, flat embeddings, and Steinberg's conjecture

  2014cites this paper
• A Practical Torus Embedding Algorithm and Its Implementation

  2014cites this paper
• Embedding and canonizing graphs of bounded genus in logspace

  2014cites this paper
• The Complexity of Toroidality Testing

  2014cites this paper
• Toroidal grid minors and stretch in embedded graphs

  2014cites this paper
• Graph minors , decompositions and algorithms ( Lecture notes )

  2014cites this paper
• Beyond the Euler Characteristic: Approximating the Genus of General Graphs

  2014influential citation
• Graphs whose complement and square are isomorphic

  2014cites this paper
• 4-connected projective-planar graphs are Hamiltonian-connected

  2013cites this paper
• Independence and Cliques

  2013cites this paper
• Graph-Based Representations in Pattern Recognition

  2013cites this paper
• Distance in Graphs

  2013cites this paper
• The Graph Crossing Number and its Variants: A Survey

  2013cites this paper
• 2 Crossings and Planarization

  2013cites this paper
• Block Additivity of Z2-Embeddings

  2013cites this paper
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)

  2013cites this paper
• Three-Dimensional Drawings

  2013cites this paper
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

  2013cites this paper
• Graphs Whose Complement and Square Are Isomorphic (extended Version) Graphs Whose Complement and Square Are Isomorphic (extended Version)

  2013cites this paper
• Matrix sparsification and nested dissection over arbitrary fields

  2013cites this paper
• Block Additivity of ℤ2-Embeddings

  2013cites this paper
• A Pseudo-Approximation for the Genus of Hamiltonian Graphs

  2013cites this paper
• Crossings and Planarization

  2013cites this paper
• On the Complexity of Submap Isomorphism

  2013cites this paper
• Approximation Algorithms for Euler Genus and Related Problems

  2013influential citation
• Factors and Factorization

  2013cites this paper
• Contraction checking in graphs on surfaces

  2012cites this paper
• Graph Minors and Parameterized Algorithm Design

  2012cites this paper
• The Birth and Early Years of Parameterized Complexity

  2012cites this paper
• Five-coloring graphs on the Klein bottle

  2012cites this paper
• Linkless and Flat Embeddings in 3-Space

  2012influential citation
• A Complete Bibliography of Publications in the SIAM Journal on Discrete Mathematics

  2012cites this paper
• Embeddings of cubic Halin graphs: Genus distributions

  2012cites this paper