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, 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, 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, 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, Menus of kuratowski subgraphs
Cites Work
