On Degree Properties of Crossing-critical Families of Graphs

BOKAL, Drago, Mojca BRAČIČ, Marek DERŇÁR a Petr HLINĚNÝ. On Degree Properties of Crossing-critical Families of Graphs. In Emilio Di Giacomo, Anna Lubiw. Graph Drawing and Network Visualization 2015, Lecture Notes in Computer Science 9411. LNCS 9411. Berlin: Springer Verlag, 2015, s. 75-86. ISBN 978-3-319-27260-3. Dostupné z: https://dx.doi.org/10.1007/978-3-319-27261-0_7.

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

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/15:00080985

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-27260-3

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-27261-0_7

UT WoS

000373628600007

Klíčová slova anglicky

Crossing number; Tile drawing; Degree-universality; Average degree; Crossing-critical graph

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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