The graph genus problem is NP-complete
From MaRDI portal
Publication:3031932
DOI10.1016/0196-6774(89)90006-0zbMath0689.68071OpenAlexW2088455492WikidataQ56094152 ScholiaQ56094152MaRDI QIDQ3031932
Publication date: 1989
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(89)90006-0
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (86)
An inductive definition of cubic toroidal maps ⋮ A practical algorithm for the computation of the genus ⋮ Local Rings with Genus Two Zero Divisor Graph ⋮ A note on approximating graph genus ⋮ Unnamed Item ⋮ Computing crossing numbers in quadratic time ⋮ ATonnetzmodel for pentachords ⋮ Unnamed Item ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ The genus of a random graph ⋮ On the complexity of graph embeddings ⋮ Stratified graphs for imbedding systems ⋮ On the number of genus embeddings of complete bipartite graphs ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Finite commutative rings whose unitary Cayley graphs have positive genus ⋮ Minimal quadrangulations of surfaces ⋮ On the orientable genus of graphs with bounded nonorientable genus ⋮ Orienting cycle elements in orientable rotation systems ⋮ A note on the directed genus of K_n,n,n and K_n ⋮ Deciding Parity of Graph Crossing Number ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Enumerating graph embeddings and partial-duals by genus and Euler genus ⋮ Genus of the Cartesian product of triangles ⋮ Algorithmic graph embeddings ⋮ On combinatorial properties of binary spaces ⋮ Embedding graphs in the torus in linear time ⋮ Finding non-orientable surfaces in 3-manifolds ⋮ Total embedding distributions of Ringel ladders ⋮ Planarization of graphs embedded on surfaces ⋮ Obtaining a Planar Graph by Vertex Deletion ⋮ Genus polynomials of ladder-like sequences of graphs ⋮ Blocking nonorientability of a surface ⋮ The Bundled Crossing Number ⋮ Obtaining a planar graph by vertex deletion ⋮ Finding large planar subgraphs and large subgraphs of a given genus ⋮ Characterization of signed Gauss paragraphs and skew-symmetric graded matrices ⋮ Unnamed Item ⋮ Bundled crossings revisited ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Embeddings of graphs with no short noncontractible cycles ⋮ Limit points for average genus. I: 3-connected and 2-connected simplicial graphs ⋮ Faster parameterized algorithms for minor containment ⋮ Finite groups whose noncyclic graphs have positive genus ⋮ On the genus of the zero-divisor graph of \(\mathbb Z_n\) ⋮ The Genus of a Random Bipartite Graph ⋮ Lower bound of the number of maximum genus embeddings and genus embeddings of \(K_{12s+7}\) ⋮ Counting orientable embeddings by genus for a type of 3-regular graph ⋮ Bundled Crossings Revisited ⋮ Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus ⋮ Power graphs of (non)orientable genus two ⋮ The genus polynomials of cross-ladder digraphs in orientable surfaces ⋮ On the minimum load coloring problem ⋮ Genus embeddings of a type of graph ⋮ The genus distributions of directed antiladders in orientable surfaces ⋮ A survey on the Intersection graphs of ideals of rings ⋮ Algorithmic graph embeddings ⋮ The genus distributions for a certain type of permutation graphs in orientable surfaces ⋮ The Zero Divisor Graphs of Commutative Local Rings of Orderp4andp5 ⋮ The genus of a type of graph ⋮ On the page number of RNA secondary structures with pseudoknots ⋮ ON THE GENUS OF THE INTERSECTION GRAPH OF IDEALS OF A COMMUTATIVE RING ⋮ Counterexamples to the nonorientable genus conjecture for complete tripartite graphs ⋮ Unnamed Item ⋮ On maximum planar induced subgraphs ⋮ Hanani-Tutte for approximating maps of graphs ⋮ A note on directed genera of some tournaments ⋮ The genus of complete 3-uniform hypergraphs ⋮ Genera of Cayley maps ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ Unnamed Item ⋮ New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces ⋮ On the embedding genus distribution of ladders and crosses ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ Unnamed Item ⋮ Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface ⋮ Finite commutative rings with higher genus unit graphs ⋮ Dynamic programming for graphs on surfaces ⋮ Crossing Layout in Non-planar Graph Drawings ⋮ A survey on genus of selected graphs from commutative rings ⋮ Face covers and the genus problem for apex graphs ⋮ Embedding digraphs on orientable surfaces ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ A relative maximum genus graph embedding and its local maximum genus ⋮ On embeddings of circulant graphs ⋮ Embeddings of graphs
This page was built for publication: The graph genus problem is NP-complete
