The graph genus problem is NP-complete
From MaRDI portal
Cited in
(only showing first 100 items - show all)- On the embedding genus distribution of ladders and crosses
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
- Embeddings of graphs
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- On the orientable genus of graphs with bounded nonorientable genus
- Orienting cycle elements in orientable rotation systems
- Algorithmic graph embeddings
- Blocking nonorientability of a surface
- A relative maximum genus graph embedding and its local maximum genus
- An inductive definition of cubic toroidal maps
- Finite commutative rings whose unitary Cayley graphs have positive genus
- Finding non-orientable surfaces in 3-manifolds
- Counterexamples to the nonorientable genus conjecture for complete tripartite graphs
- A note on directed genera of some tournaments
- 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.
- Computing crossing numbers in quadratic time
- The genus of a random graph
- Stratified graphs for imbedding systems
- A survey on genus of selected graphs from commutative rings
- Minimal quadrangulations of surfaces
- Genus polynomials of ladder-like sequences of graphs
- Bundled crossings revisited
- Finite groups whose noncyclic graphs have positive genus
- The genus of complete 3-uniform hypergraphs
- On embeddings of circulant graphs
- Obtaining a planar graph by vertex deletion
- On the minimum load coloring problem
- The genus distributions of directed antiladders in orientable surfaces
- The genus distributions for a certain type of permutation graphs in orientable surfaces
- On maximum planar induced subgraphs
- Genera of Cayley maps
- On the number of genus embeddings of complete bipartite graphs
- Genus characterizes the complexity of certain graph problems: Some tight results
- Face-width of embedded graphs
- Maximum genus of regular graphs
- A note on approximating graph genus
- The Bundled Crossing Number
- Local Rings with Genus Two Zero Divisor Graph
- A Tonnetz model for pentachords
- Obtaining a Planar Graph by Vertex Deletion
- Total embedding distributions of Ringel ladders
- Space complexity of perfect matching in bounded genus bipartite graphs
- 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
- Characterization of signed Gauss paragraphs and skew-symmetric graded matrices
- Power graphs of (non)orientable genus two
- On the genus of the zero-divisor graph of \(\mathbb Z_n\)
- The zero divisor graphs of commutative local rings of order \(p^4\) and \(p^5\)
- Crossing Layout in Non-planar Graph Drawings
- A practical algorithm for the computation of the genus
- On the complexity of graph embeddings
- Stronger ILPs for the Graph Genus Problem.
- Compressed Decision Problems in Hyperbolic Groups.
- Enumerating graph embeddings and partial-duals by genus and Euler genus
- Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems
- On combinatorial properties of binary spaces
- Embedding graphs in the torus in linear time
- Embedding graphs into two-dimensional simplicial complexes
- Hanani-Tutte for approximating maps of graphs
- The genus of a random bipartite graph
- Bundled crossings revisited
- New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
- On the genus of the intersection graph of ideals of a commutative ring
- scientific article; zbMATH DE number 2192203 (Why is no real title available?)
- Finite commutative rings with higher genus unit graphs
- Dynamic programming for graphs on surfaces
- scientific article; zbMATH DE number 2230213 (Why is no real title available?)
- Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface
- scientific article; zbMATH DE number 7662167 (Why is no real title available?)
- Algorithmic graph embeddings
- A survey on the Intersection graphs of ideals of rings
- Planarization of graphs embedded on surfaces
- Finding large planar subgraphs and large subgraphs of a given genus
- Faster parameterized algorithms for minor containment
- 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
- Asymptotics of local face distributions and the face distribution of the complete graph
- Finite abelian groups with positive genus subgroup intersection graphs
- A topological property of a hypergraph assigned to commutative rings
- Bounds on the genus for 2-cell embeddings of prefix-reversal graphs
- Immersions of bipartite graphs and numismatics
- Finite commutative rings whose line graphs of comaximal graphs have genus at most two
- On the page number of RNA secondary structures with pseudoknots
- Efficient polynomial-time approximation scheme for the genus of dense graphs
- Genus and crosscap of normal subgroup based power graphs of finite groups
- Nilpotent groups whose difference graphs have positive genus
- The minimum orientable genus of the repeated Cartesian product of graphs
- A general design method for scaffold-free DNA wireframe nanostructures
- On the genus of Cartesian products of complete graph \(K_{12t+7}\) with cycles and paths
- An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
- An efficient genus algorithm based on graph rotations
- Genus of the Cartesian product of triangles
- Embeddings of graphs with no short noncontractible cycles
- Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
- The genus polynomials of cross-ladder digraphs in orientable surfaces
- Genus embeddings of a type of graph
- The genus of a type of graph
This page was built for publication: The graph genus problem is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3031932)
