D 2016

The Crossing Number of the Cone of a Graph

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

Základní údaje

Originální název

The Crossing Number of the Cone of a Graph

Autoři

ALFARO, Carlos A. (484 Mexiko), Alan ARROYO (484 Mexiko), Marek DERŇÁR (703 Slovensko, garant, domácí) a Bojan MOHAR (124 Kanada)

Vydání

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

Nakladatel

Springer Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/16:00088630

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-50105-5

ISSN

DOI

UT WoS

000405478500033

Klíčová slova anglicky

Crossing number; apex graph

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 13. 5. 2020 19:27, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Česky

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.

Návaznosti

GA14-03501S, projekt VaV
Název: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
Investor: Grantová agentura ČR, Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
MUNI/A/0935/2015, interní kód MU
Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Akronym: SKOMU)
Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty