On Degree Properties of Crossing-Critical Families of Graphs

Bokal, Drago and Bračič, Mojca and Derňár, Marek and Hliněný, Petr (2015) On Degree Properties of Crossing-Critical Families of Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 75-86(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_7).

Full text not available from this repository.


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∈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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1479

Actions (login required)

View Item View Item