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, Los Angeles, CA, USA , 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
Keywords:Crossing number Tile drawing Degree-universality Average degree Crossing-critical graph
Classifications:G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
ID Code:1479

Repository Staff Only: item control page


Ajtai, M., Chvátal, V., Newborn, M., Szemerédi, E.: Crossing-free subgraphs.In: Theory and Practice of Combinatorics. North-Holland Mathematics Studies, vol.60, pp. 9–12. North-Holland (1982)

Bokal, D.: On the crossing numbers of cartesian products with paths. J. Comb. Theory Ser. B 97(3), 381–384 (2007)

Bokal, D.: Infinite families of crossing-critical graphs with prescribed average degree and crossing number. J. Graph Theory 65(2), 139–162 (2010)

Bokal, D., Chimani, M., Leaños, J.: Crossing number additivity over edge cuts. Eur. J. Comb. 34(6), 1010–1018 (2013)

Bokal, D., Oporowski, B., Richter, R.B., Salazar, G.: Characterizing 2-crossing-critical graphs. Manuscript, 171 p. http://​arxiv.​org/​abs/​1312.​3712 (2013)

Dvořák, Z., Mohar, B.: Crossing-critical graphs with large maximum degree. J. Comb. Theory, Ser. B 100(4), 413–417 (2010)

Geelen, J.F., Richter, R.B., Salazar, G.: Embedding grids in surfaces. Eur. J. Comb. 25(6), 785–792 (2004)

Hernández-Vélez, C., Salazar, G., Thomas, R.: Nested cycles in large triangulations and crossing-critical graphs. J. Comb. Theory, Ser. B 102(1), 86–92 (2012)

Hlinecaronný, P.: Crossing-critical graphs and path-width. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 102–114. Springer, Heidelberg (2002)

Hliněný, P.: Crossing-number critical graphs have bounded path-width. J. Comb. Theory Ser. B 88(2), 347–367 (2003)

Hliněný, P.: New infinite families of almost-planar crossing-critical graphs. Electr. J. Comb. 15 R102 (2008)

Hliněný, P., Salazar, G.: Stars and bonds in crossing-critical graphs. J. Graph Theory 65(3), 198–215 (2010)

Kochol, M.: Construction of crossing-critical graphs. Discrete Math. 66(3), 311–313 (1987)

Leighton, T.: Complexity Issues in VLSI. Foundations of Computing Series. MIT Press, Cambridge (1983)

Pinontoan, B., Richter, R.B.: Crossing numbers of sequences of graphs II: Planar tiles. J. Graph Theory 42(4), 332–341 (2003)

Pinontoan, B., Richter, R.B.: Crossing numbers of sequences of graphs I: General tiles. Australas. J. Comb. 30, 197–206 (2004)

Richter, R.B., Thomassen, C.: Minimal graphs with crossing number at least k. J. Comb. Theory Ser. B 58(2), 217–224 (1993)

Salazar, G.: Infinite families of crossing-critical graphs with given average degree. Discrete Math. 271(1–3), 343–350 (2003)

Širáň, J.: Infinite families of crossing-critical graphs with a given crossing number. Discrete Math. 48(1), 129–132 (1984)