Publication details

The Crossing Number of the Cone of a Graph



Year of publication 2016
Type Article in Proceedings
Conference Graph Drawing and Network Visualization - 24th International Symposium, GD 2016
MU Faculty or unit

Faculty of Informatics

Field Informatics
Keywords Crossing number; apex graph
Description Motivated by a problem asked by Richter and by the long standing Harary-Hill conjecture, we study the relation between the crossing number of a graph G and the crossing number of its cone CG, the graph obtained from G by adding a new vertex adjacent to all the vertices in G. Simple examples show that the difference cr(CG)-cr(G) can be arbitrarily large for any fixed k=cr(G). In this work, we are interested in finding the smallest possible difference, that is, for each non-negative integer k, find the smallest f(k) for which there exists a graph with crossing number at least k and cone with crossing number f(k). For small values of k, we give exact values of f(k) when the problem is restricted to simple graphs, and show that f(k)=k+Theta(sqrt(k)) when multiple edges are allowed.
Related projects: