Crossing Number is NP-Complete
From MaRDI portal
Publication:3320398
DOI10.1137/0604033zbMath0536.05016WikidataQ57255585 ScholiaQ57255585MaRDI QIDQ3320398
David S. Johnson, Michael R. Garey
Publication date: 1983
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0604033
68Q25: Analysis of algorithms and problem complexity
05C10: Planar graphs; geometric and topological aspects of graph theory
Related Items
On Canonical Concurrent Flows, Crossing Number and Graph Expansion, Unnamed Item, Genetic algorithms for drawing bipartite graphs, Enumerations of the maximum rectilinear crossing numbers of complete and complete multi-partite graphs, Approximating the Crossing Number of Toroidal Graphs, Crossing Number of Graphs with Rotation Systems, Unnamed Item, Recognizing string graphs in NP, Experiments on drawing 2-level hierarchical graphs, Experiments on drawing 2-level hierarchical graphs, On the crossing number of complete graphs, A branch-and-cut approach to the crossing number problem, On the parameterized complexity of layered graph drawing, The crossing number of \(K_{1,m,n}\), Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, Graph graphics: Theory and practice, Representations of graphs and networks (coding, layouts and embeddings), Some provably hard crossing number problems, Graph layout for applications in compiler construction, Edge crossings in drawings of bipartite graphs, Drawing graphs in two layers, The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings, ARC crossing minimization in hierarchical digraphs with tabu search, Crossing-number critical graphs have bounded path-width, A successful concept for measuring non-planarity of graphs: The crossing number., A new lower bound for the bipartite crossing number with applications, The crossing number of \(C(n; \{1,3\})\), On the one-sided crossing minimization in a bipartite graph with large degrees, Which crossing number is it anyway?, New bounds on the barycenter heuristic for bipartite graph drawing., Decidability of string graphs, NETPAD: An interactive graphics system for network modeling and optimization, Drawings of graphs on surfaces with few crossings, Crossing-constrained hierarchical drawings, The crossing number of \(C(3k+1;\{1,k\})\), The crossing number of \(K_{1,4,n}\), The crossing number of Cartesian products of complete bipartite graphs \(K_{2,m}\) with paths \(P_{n}\), Odd crossing number and crossing number are not the same, Minimizing crossings in hierarchical digraphs with a hybridized genetic algorithm, Crossing number is hard for cubic graphs, On maximum planar induced subgraphs, Orthogonal drawings of graphs with vertex and edge labels, Unnamed Item, Unnamed Item, On the Minimum Cut of Planarizations, How to draw a hypergraph, Obtaining a Planar Graph by Vertex Deletion, An improved upper bound on the crossing number of the hypercube, Crossing and Weighted Crossing Number of Near-Planar Graphs, Menus of kuratowski subgraphs
Cites Work
