On Degree Properties of Crossing-critical Families of Graphs

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BOKAL Drago BRAČIČ Mojca DERŇÁR Marek HLINĚNÝ Petr

Year of publication 2015
Type Article in Proceedings
Conference Graph Drawing and Network Visualization 2015, Lecture Notes in Computer Science 9411
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-319-27261-0_7
Field Informatics
Keywords Crossing number; Tile drawing; Degree-universality; Average degree; Crossing-critical graph
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.