The Crossing Number of the Cone of a Graph

Alfaro, Carlos A. and Arroyo, Alan and Derňár, Marek and Mohar, Bojan (2016) The Crossing Number of the Cone of a Graph. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 427-438(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_33).

Full text not available from this repository.

Abstract

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+Θ(√k) when multiple edges are allowed.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1560

Actions (login required)

View Item View Item