On Degree Properties of Crossing-Critical Families of Graphs

被引:1
作者
Bokal, Drago [1 ]
Bracic, Mojca [1 ]
Dernar, Marek [2 ]
Hlineny, Petr [2 ]
机构
[1] Univ Maribor, Fac Nat Sci & Math, SLO-2000 Maribor, Slovenia
[2] Masaryk Univ, Fac Informat, Brno, Czech Republic
来源
GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2015 | 2015年 / 9411卷
关键词
Crossing number; Tile drawing; Degree-universality; Average degree; Crossing-critical graph; INFINITE FAMILIES; AVERAGE DEGREE; PATH-WIDTH; NUMBER;
D O I
10.1007/978-3-319-27261-0_7
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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, 4 is an element of D, 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.
引用
收藏
页码:75 / 86
页数:12
相关论文
共 19 条