Crossing Number is NP-Complete
From MaRDI portal
Recommendations
Cites work
Cited in
(only showing first 100 items - show all)- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- On the complexity of crossings in permutations
- Non-planar core reduction of graphs
- The crossing number of \(C(8,2)\square P_{n}\)
- Threshold and complexity results for the cover pebbling game
- The crossing numbers of generalized Petersen graphs with small order
- An evolutionary formulation of the crossing number problem
- Crossing minimization in weighted bipartite 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
- Analogies between the crossing number and the tangle crossing number
- Heuristics for the constrained incremental graph drawing problem
- Tabu search for the dynamic bipartite drawing problem
- The crossing number of locally twisted cubes \(L T Q_n\)
- Variable neighborhood descent for the incremental graph drawing
- Variable neighborhood scatter search for the incremental graph drawing problem
- The crossing number of join of the generalized Petersen graph \(P(3, 1)\) with path and cycle
- The crossing number of the hexagonal graph \(H_{3,n}\)
- Crossing numbers and stress of random graphs
- The crossing number of \(C(n; \{1,3\})\)
- On the one-sided crossing minimization in a bipartite graph with large degrees
- Gap-planar graphs
- 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
- Hardness of approximation for crossing number
- Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
- Testing gap \(k\)-planarity is NP-complete
- The crossing number of hexagonal graph \(H_{3,n }\) in the projective plane
- The crossing numbers of join of special disconnected graph on five vertices with discrete graphs
- Star-struck by fixed embeddings: modern crossing number heuristics
- Cyclic permutations in determining crossing numbers
- The slotted online one-sided crossing minimization problem on 2-regular graphs
- Parameterized analysis and crossing minimization problems
- The crossing number of \(K_{5,n+1} \setminus e\)
- A crossing lemma for multigraphs
- On the 2-colored crossing number
- Exact crossing number parameterized by vertex cover
- Rotation and crossing numbers for join products
- The crossing number of Cartesian product of 5-wheel with any tree
- Relaxing the constraints of clustered planarity
- Weighted Turán problems with applications
- Fan-planarity: properties and complexity
- Two recursive inequalities for crossing numbers of graphs
- On the recognition of fan-planar and maximal outer-fan-planar graphs
- Inapproximability ratios for crossing number
- Set labelling vertices to ensure adjacency coincides with disjointness
- Obtaining a planar graph by vertex deletion
- The early history of the brick factory problem
- The crossing number of the Cartesian product of paths with complete graphs
- 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
- There are no cubic graphs on 26 vertices with crossing number 10 or 11
- A variable depth neighborhood search algorithm for the min-max arc crossing problem
- Crossings between non-homotopic edges
- A satisfiability formulation of problems on level graphs
- On Eggleton and Guy's conjectured upper bound for the crossing number of the n-cube
- Approximating the maximum rectilinear crossing number
- The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
- A faster fixed parameter algorithm for two-layer crossing minimization
- An upper bound for the crossing number of augmented cubes
- Crossing Minimization in Storyline Visualization
- On the Pseudolinear Crossing Number
- A satisfiability-based approach for embedding generalized tanglegrams on level graphs
- Crossing numbers of imbalanced graphs
- The straight-line RAC drawing problem is NP-hard
- k-level crossing minimization is NP-hard for trees
- An effective crossing minimisation heuristic based on star insertion
- The crossing number of chordal ring networks
- Monotone Crossing Number
- scientific article; zbMATH DE number 7225866 (Why is no real title available?)
- Noncrossing Subgraphs in Topological Layouts
- On the crossing numbers of join products of four graphs of order six with the discrete graph
- On the Minimum Cut of Planarizations
- Simultaneous embedding of embedded planar graphs
- 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
- The Crossing Number of Graphs: Theory and Computation
- Bipartite Graph Representation of Multiple Decision Table Classifiers
- Menus of kuratowski subgraphs
This page was built for publication: Crossing Number is NP-Complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3320398)
