The Crossing Number of the Cone of a Graph

D 2016

The Crossing Number of the Cone of a Graph

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

Basic information

Original name

The Crossing Number of the Cone of a Graph

Authors

ALFARO, Carlos A. (484 Mexico), Alan ARROYO (484 Mexico), Marek DERŇÁR (703 Slovakia, guarantor, belonging to the institution) and Bojan MOHAR (124 Canada)

Edition

LNCS 9801. Berlin, Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, p. 427-438, 12 pp. 2016

Publisher

Springer Verlag

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/16:00088630

Organization unit

Faculty of Informatics

ISBN

978-3-319-50105-5

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-50106-2_33

UT WoS

000405478500033

Keywords in English

Crossing number; apex graph

Abstract

ORIG CZ

V originále

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.

In Czech

Studuje se vztah průsečíkového čísla grafu k průsečíkovému číslu po přidání vrcholu spojeného se všemi ostatními.

Links

GA14-03501S, research and development project

Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Investor: Czech Science Foundation

MUNI/A/0935/2015, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

Citovat

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. 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.

@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.

Detailed Information on Publication Record