On Degree Properties of Crossing-critical Families of Graphs

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

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

Změněno: 14. 2. 2017 08:59, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

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

Citovat

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.

@inproceedings{1309625,
   author = {Bokal, Drago and Bračič, Mojca and Derňár, Marek and Hliněný, Petr},
   address = {Berlin},
   booktitle = {Graph Drawing and Network Visualization 2015, Lecture Notes in Computer Science 9411},
   doi = {http://dx.doi.org/10.1007/978-3-319-27261-0_7},
   edition = {LNCS 9411},
   editor = {Emilio Di Giacomo, Anna Lubiw},
   keywords = {Crossing number; Tile drawing; Degree-universality; Average degree; Crossing-critical graph},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-319-27260-3},
   pages = {75-86},
   publisher = {Springer Verlag},
   title = {On Degree Properties of Crossing-critical Families of Graphs},
   year = {2015}
}

TY  - JOUR
ID  - 1309625
AU  - Bokal, Drago - Bračič, Mojca - Derňár, Marek - Hliněný, Petr
PY  - 2015
TI  - On Degree Properties of Crossing-critical Families of Graphs
PB  - Springer Verlag
CY  - Berlin
SN  - 9783319272603
KW  - Crossing number
KW  - Tile drawing
KW  - Degree-universality
KW  - Average degree
KW  - Crossing-critical graph
N2  - 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.
ER  -

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. \textit{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.

Podrobný výpis o publikaci