Crossing Number is NP-Complete
From MaRDI portal
Publication:3320398
DOI10.1137/0604033zbMath0536.05016OpenAlexW2060538865WikidataQ57255585 ScholiaQ57255585MaRDI QIDQ3320398
Michael R. Garey, David S. Johnson
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
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics, Unnamed Item, SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS, Enumerations of the maximum rectilinear crossing numbers of complete and complete multi-partite graphs, How to draw a hypergraph, Crossing Numbers of Beyond-Planar Graphs Revisited, Deciding Parity of Graph Crossing Number, The crossing numbers of join products of paths with three graphs of order five, Reviews, Genetic algorithms for drawing bipartite graphs, On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem, Monotone Crossing Number, Zip product of graphs and crossing numbers, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Bounding the tripartite‐circle crossing number of complete tripartite graphs, Crossing edge minimization in radial outerplanar layered graphs using segment paths, Inserting Multiple Edges into a Planar Graph, Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes, Planarity for clustered graphs, Planar tanglegram layouts and single edge insertion, On Canonical Concurrent Flows, Crossing Number and Graph Expansion, The crossing numbers of join products of four graphs of order five with paths and cycles, Obtaining a Planar Graph by Vertex Deletion, The crossing number of the generalized Petersen graph P(3k,k) in the projective plane, Characterizing planar tanglegram layouts and applications to edge insertion problems, Crossing Minimization in Storyline Visualization, On the 2-layer window width minimization problem, Maximum Cut Parameterized by Crossing Number, On the Pseudolinear Crossing Number, Unnamed Item, Unnamed Item, Menus of kuratowski subgraphs, Approximating the Crossing Number of Toroidal Graphs, Crossing minimization in perturbed drawings, ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS, A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs, Unnamed Item, Crossing minimization in perturbed drawings, Unnamed Item, Crossing numbers of imbalanced graphs, Inserting an edge into a geometric embedding, An improved upper bound on the crossing number of the hypercube, Inserting an edge into a geometric embedding, Crossing and Weighted Crossing Number of Near-Planar Graphs, Recognizing string graphs in NP, Approximation algorithms for minimizing edge crossings in radial drawings, Crossing Number of Graphs with Rotation Systems, On the crossing number of join product of the discrete graph with special graphs of order five, The Straight-Line RAC Drawing Problem Is NP-Hard, k-Level Crossing Minimization Is NP-Hard for Trees, A survey of graphs with known or bounded crossing numbers, ON THE CROSSING NUMBER OF THE CARTESIAN PRODUCT OF A SUNLET GRAPH AND A STAR GRAPH, Experiments on drawing 2-level hierarchical graphs, Connecting the dots (with minimum crossings), Experiments on drawing 2-level hierarchical graphs, The Crossing Number of Graphs: Theory and Computation, Bipartite Graph Representation of Multiple Decision Table Classifiers, Unnamed Item, Unnamed Item, Fan-Planar Graphs, Crossing Layout in Non-planar Graph Drawings, Beyond Clustered Planar Graphs, An effective crossing minimisation heuristic based on star insertion, On the crossing numbers of join products of W_{4}+P_{n} and W_{4}+C_{n}, Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill, Crossings Between Non-homotopic Edges, On the Minimum Cut of Planarizations, A crossing lemma for multigraphs, Two recursive inequalities for crossing numbers of graphs, Drawing graphs in two layers, A faster fixed parameter algorithm for two-layer crossing minimization, Recognizing and drawing IC-planar graphs, Analogies between the crossing number and the tangle crossing number, Decidability of string graphs, Heuristics for the constrained incremental graph drawing problem, The crossing number of chordal ring networks, The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings, Star-struck by fixed embeddings: modern crossing number heuristics, Graph graphics: Theory and practice, NETPAD: An interactive graphics system for network modeling and optimization, Tabu search for the dynamic bipartite drawing problem, Cyclic permutations in determining crossing numbers, Unnamed Item, There are no cubic graphs on 26 vertices with crossing number 10 or 11, ARC crossing minimization in hierarchical digraphs with tabu search, The slotted online one-sided crossing minimization problem on 2-regular graphs, Parameterized analysis and crossing minimization problems, The crossing number of locally twisted cubes \(L T Q_n\), Drawings of graphs on surfaces with few crossings, On the recognition of fan-planar and maximal outer-fan-planar graphs, The crossing number of \(K_{5,n+1} \setminus e\), A variable depth neighborhood search algorithm for the min-max arc crossing problem, Inapproximability ratios for crossing number, Set labelling vertices to ensure adjacency coincides with disjointness, Crossings between non-homotopic edges, On drawings and decompositions of 1-planar graphs, Variable neighborhood descent for the incremental graph drawing, A crossing lemma for multigraphs, A rearrangement of adjacency matrix based approach for solving the crossing minimization problem, Unnamed Item, Crossing-number critical graphs have bounded path-width, The complexity of power indexes with graph restricted coalitions, Variable neighborhood scatter search for the incremental graph drawing problem, Hardness of approximation for crossing number, Obtaining a planar graph by vertex deletion, On crossing numbers of geometric proximity graphs, The early history of the brick factory problem, On the 2-colored crossing number, Exact crossing number parameterized by vertex cover, 1-fan-bundle-planar drawings of graphs, The crossing number of join of the generalized Petersen graph \(P(3, 1)\) with path and cycle, Rotation and crossing numbers for join products, Planar crossing numbers of graphs of bounded genus, The crossing number of Cartesian product of 5-wheel with any tree, A successful concept for measuring non-planarity of graphs: The crossing number., The crossing number of the hexagonal graph \(H_{3,n}\), The crossing number of the Cartesian product of paths with complete graphs, Crossing numbers and stress of random graphs, Representations of graphs and networks (coding, layouts and embeddings), Some provably hard crossing number problems, Vertex insertion approximates the crossing number of apex graphs, Crossing-constrained hierarchical drawings, The crossing number of \(C(3k+1;\{1,k\})\), Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation, A branch-and-cut approach to the crossing number problem, On the parameterized complexity of layered graph drawing, 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}\), MSOL restricted contractibility to planar graphs, On the red/blue spanning tree problem, Odd crossing number and crossing number are not the same, The crossing number of \(C(n; \{1,3\})\), Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization, Relaxing the constraints of clustered planarity, Crossing numbers of graphs with rotation systems, Crossing number and weighted crossing number of near-planar graphs, Randomized priority algorithms, Minimizing crossings in hierarchical digraphs with a hybridized genetic algorithm, On the one-sided crossing minimization in a bipartite graph with large degrees, Crossing number is hard for cubic graphs, Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation, On maximum planar induced subgraphs, Gap-planar graphs, Testing gap \(k\)-planarity is NP-complete, The crossing number of \(K_{1,m,n}\), Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, On the complexity of crossings in permutations, Non-planar core reduction of graphs, A linear edge kernel for two-layer crossing minimization, The crossing number of \(C(8,2)\square P_{n}\), Approximating the Maximum Rectilinear Crossing Number, The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube, The crossing number of hexagonal graph \(H_{3,n }\) in the projective plane, Threshold and complexity results for the cover pebbling game, The crossing numbers of generalized Petersen graphs with small order, Weighted Turán problems with applications, Graph layout for applications in compiler construction, An evolutionary formulation of the crossing number problem, A new lower bound for the bipartite crossing number with applications, Crossing minimization in weighted bipartite graphs, Orthogonal drawings of graphs with vertex and edge labels, Which crossing number is it anyway?, New bounds on the barycenter heuristic for bipartite graph drawing., Fan-planarity: properties and complexity, An upper bound for the crossing number of augmented cubes, The crossing numbers of join of special disconnected graph on five vertices with discrete graphs, Edge crossings in drawings of bipartite graphs, On the crossing number of complete graphs
Cites Work
