𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Crossing numbers of imbalanced graphs

✍ Scribed by János Pach; József Solymosi; Gábor Tardos

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
103 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e>4__n__ edges is at least constant times e^3^/n^2^. Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d~1~⩾d~2~⩾···⩾d~n~, then the crossing number satisfies with , and that this bound is tight apart from the values of the constants c~1~, c~2~>0. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010

📜 SIMILAR VOLUMES

Crossing numbers of Sierpiński-like grap
Crossing numbers of Sierpiński-like graphs
✍ Sandi Klavžar; Bojan Mohar 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## Abstract Crossing numbers of Sierpiński graphs __S__(__n__,__k__) and their regularizations __S__^+^(__n__,__k__) and __S__^++^(__n__,__k__) are studied. Drawings of these graphs are presented and proved to be optimal for __S__^+^(__n__,__k__) and __S__^++^(__n__,__k__) for every __n__ ≥ 1 and _

Crossing numbers of sequences of graphs
Crossing numbers of sequences of graphs II: Planar tiles
✍ Benny Pinontoan; R. Bruce Richter 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the __tile__, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of __k__‐crossing‐critical graphs. Furt

The book crossing number of a graph
The book crossing number of a graph
✍ Shahrokhi, Farhad; Sz�kely, L�szl� A.; S�kora, Ondrej; Vrt'o, Imrich 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are t w o polynomi

On graphs whose line graphs have crossin
On graphs whose line graphs have crossing number one
✍ Stanislav Jendrol'; Marián Kles̆c̆ 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract Necessary and sufficient conditions are given for a nonplanar graph to have a line graph with crossing number one. This corrects some errors in Kulli et al. 4. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 181–188, 2001