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 and Petr HLINĚNÝ

Basic information

Original name

On Degree Properties of Crossing-critical Families of Graphs

Authors

BOKAL, Drago (705 Slovenia), Mojca BRAČIČ (705 Slovenia), Marek DERŇÁR (703 Slovakia, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution)

Edition

LNCS 9411. Berlin, Graph Drawing and Network Visualization 2015, Lecture Notes in Computer Science 9411, p. 75-86, 12 pp. 2015

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

Organization unit

Faculty of Informatics

ISBN

978-3-319-27260-3

ISSN

DOI

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

UT WoS

000373628600007

Keywords in English

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

Abstract

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.

In Czech

Konstruhujeme nekonečné třídy průsečíkově kritických grafů s danými vlastnostmi stupňů.

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/1206/2014, interní kód MU

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

Investor: Masaryk University, Category A

Citovat

BOKAL, Drago, Mojca BRAČIČ, Marek DERŇÁR and 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, p. 75-86. ISBN 978-3-319-27260-3. Available from: 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 and 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, p.~75-86. ISBN~978-3-319-27260-3. Available from: https://dx.doi.org/10.1007/978-3-319-27261-0\_{}7.

Detailed Information on Publication Record