D
2015
On Degree Properties of Crossing-critical Families of Graphs
BOKAL, Drago, Mojca BRAČIČ, Marek DERŇÁR a Petr HLINĚNÝ
Základní údaje
Originální název
On Degree Properties of Crossing-critical Families of Graphs
Autoři
BOKAL, Drago (705 Slovinsko), Mojca BRAČIČ (705 Slovinsko), Marek DERŇÁR (703 Slovensko, domácí) a
Petr HLINĚNÝ (203 Česká republika, garant, domácí)
Vydání
LNCS 9411. Berlin, Graph Drawing and Network Visualization 2015, Lecture Notes in Computer Science 9411, od s. 75-86, 12 s. 2015
Nakladatel
Springer Verlag
Další údaje
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
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/15:00080985
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
Crossing number; Tile drawing; Degree-universality; Average degree; Crossing-critical graph
Příznaky
Mezinárodní význam, Recenzováno
V originále
Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that min(D)>=3 and 3,4eD, and for all sufficiently large k there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in any large enough graph in this family. We also investigate what are the possible average degrees of such crossing-critical families.
Česky
Konstruhujeme nekonečné třídy průsečíkově kritických grafů s danými vlastnostmi stupňů.
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/1206/2014, 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 |
|
Zobrazeno: 4. 11. 2024 15:57