Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1371158,
author = {Alfaro, Carlos A. and Arroyo, Alan and Derňár, Marek and Mohar, Bojan},
address = {Berlin},
booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, GD 2016},
doi = {http://dx.doi.org/10.1007/978-3-319-50106-2_33},
edition = {LNCS 9801},
editor = {Yifan Hu and Martin Nollenburg},
keywords = {Crossing number; apex graph},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-319-50105-5},
pages = {427-438},
publisher = {Springer Verlag},
title = {The Crossing Number of the Cone of a Graph},
year = {2016}
}
TY - JOUR
ID - 1371158
AU - Alfaro, Carlos A. - Arroyo, Alan - Derňár, Marek - Mohar, Bojan
PY - 2016
TI - The Crossing Number of the Cone of a Graph
PB - Springer Verlag
CY - Berlin
SN - 9783319501055
KW - Crossing number
KW - apex graph
N2 - 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.
ER -
ALFARO, Carlos A., Alan ARROYO, Marek DERŇÁR and Bojan MOHAR. The Crossing Number of the Cone of a Graph. In Yifan Hu and Martin Nollenburg. \textit{Graph Drawing and Network Visualization - 24th International Symposium, GD 2016}. LNCS 9801. Berlin: Springer Verlag, 2016, p.~427-438. ISBN~978-3-319-50105-5. Available from: https://dx.doi.org/10.1007/978-3-319-50106-2\_{}33.
|
