19 Jul Proposal for an Algorithm for Finding the Crossing Number of a Graph
The crossing number cr(G) of a graph G is the least number of edge crossings of a plane drawing of G. Determining the exact crossing number of a graph is NP-Complete. In this project, we present a highly extensible algorithm for finding the crossing number of a graph. The algorithm works incrementally, by starting with an empty graph and adding vertices one by one in order to achieve the given graph. In every increment, we do a breadth-first search over the dual graph for each face. We go through a search tree of the possible increments to find the optimal embedding. Using an implementation of this algorithm, we can experimentally confirm Guy’s conjecture for small numbers of n. The crossing number problem has applications in incidence geometry and VLSI design.
Category: COMPUTING — Country: TURKEY — Year: 2020
OLCAY ORANSOY
Video:
Poster:
