The cylindrical crossing number of the complete bipartite graph
Athena Sparks · CSUN ScholarWorks (California State University, Northridge) · 2014
Master of Science in MathematicsA cylindrical drawing of the complete bipartite graph K m,n is a drawing with two disjoint sets of vertices placed on the top and bottom rims of a cylinder where every vertex at the top is connected to every vertex at the bottom by an edge drawn along the lateral surface of the cylinder.The cylindrical crossing number is defined as the minimum number of crossings among all cylindrical drawings of a graph.A formula is derived for the cylindrical crossing number of K m,n as well as an algorithm for creating a drawing that achieves that number.With this result, we show that among all cylindrical drawings of the complete graph K n where the edges between two vertices on the inner (or outer) boundary are contained inside (or outside) the boundary, the drawing with half (or nearly half) of the vertices on each boundary has the fewest crossings.vii