On Degree Properties of CrossingCritical Families of GraphsBokal, Drago and Bračič, Mojca and Derňár, Marek and Hliněný, Petr (2015) On Degree Properties of CrossingCritical Families of Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 7586(Official URL: http://dx.doi.org/10.1007/9783319272610_7). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_7
AbstractAnswering an open question from 2007, we construct infinite kcrossingcritical 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∈D, and for all sufficiently large k there exists a kcrossingcritical 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 crossingcritical families.
Actions (login required)
