The Crossing Number of the Cone of a Graph

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors

ALFARO Carlos A. ARROYO Alan DERŇÁR Marek MOHAR Bojan

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

Citation
Doi http://dx.doi.org/10.1007/978-3-319-50106-2_33
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: