Booth Id:
MATH036
Category:
Mathematics
Year:
2021
Finalist Names:
Oransoy, Olcay (School: Izmir Bahcesehir College 50. Year Science and Technology High School)
Abstract:
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 Won:
Innopolis University : Full tuition scholarships for the Bachelor program in Computer Science