Questions tagged [crossing-number]

Questions on crossing numbers of graphs. A crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph in question.

Filter by
Sorted by
Tagged with
3
votes
1answer
194 views

How to Prove NP-Completeness of Minimum Crossing Problem?

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia) I know that the problem of counting the Crossing ...
9
votes
1answer
8k views

How to reduce the number of crossing edges in a diagram?

I am working on a diagram editor. Diagrams display 2D shapes (nodes) connected with connectors (edges). I'd like to add an operation that, given a selection of nodes, "disentangles" them: it ...