Proposal for an Algorithm for Finding the Crossing Number of a Graph

Overview

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 is based on the fact that the best crossing number we can achieve by adding a vertex in a face F in G' will be the same regardless of where we add the vertex inside F, where G' is G but with the crossings being counted as vertices. 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 with the source being the face that we're checking, and we count the number of crossings needed to add the vertex. After we check every face, we add the vertex to the optimal face and continue to the next increment. 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.

Awards (1)

• Innopolis University : Full tuition scholarships for the Bachelor program in Computer Science

Competition history

• ISEF 2021 Mathematics · Entry MATH036

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.