✦ LIBER ✦

The book crossing number of a graph

✍ Scribed by Shahrokhi, Farhad; Sz�kely, L�szl� A.; S�kora, Ondrej; Vrt'o, Imrich

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 581 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199604)21:4<413::aid-jgt7>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

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 polynomial time algorithms to generate near optimal drawing of G on books, The first algorithm give an O(log2 n) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this algorithm w e improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O(m2/k2) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Q(m3/n2k2), provided that m = @(n2).

📜 SIMILAR VOLUMES

The Crossing Number of a Graph on a Comp

The Crossing Number of a Graph on a Compact 2-Manifold

✍ F. Shahrokhi; O. Sýkora; L.A. Székely; I. Vrťo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 478 KB

We introduce a general framework to estimate the crossing number of a graph on a compact 2-manifold in terms of the crossing number of the complete graph of the same size on the same manifold. The bounds are tight within a constant multiplicative factor for many graphs, including hypercubes, some co

Bounding the crossing number of a graph

Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree

✍ Enrique Garcia-Moreno; Gelasio Salazar 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 3 views

Crossing numbers of imbalanced graphs

✍ János Pach; József Solymosi; Gábor Tardos 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## 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,

The star chromatic number of a graph

✍ H. L. Abbott; B. Zhou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB 👁 2 views

## Abstract We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.

The chromatic covering number of a graph

✍ Reza Naserasr; Claude Tardif 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

Following [1] , we investigate the problem of covering a graph G with induced subgraphs G 1 ; . . . ; G k of possibly smaller chromatic number, but such that for every vertex u of G, the sum of reciprocals of the chromatic numbers of the G i 's containing u is at least 1. The existence of such ''ch

On the geodetic number of a graph

✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB