On Degree Properties of Crossing-critical Families of Graphs
| Authors | |
|---|---|
| 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 | |
| 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: |