𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by F. Shahrokhi; O. Sýkora; L.A. Székely; I. Vrťo

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
478 KB
Volume
123
Category
Article
ISSN
0001-8708

No coin nor oath required. For personal study only.

✦ Synopsis

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 complete bipartite graphs and random graphs. We determine the crossing number of a complete graph, and hence of many other graphs, on a compact 2-manifold up to a polylog genus multiplicative factor. We give estimations for related Tura n numbers.

1996 Academic Press, Inc.

1. Introduction

We assume that the reader is familiar with the basic concepts of graph theory as in [CL86] and the basic concepts of topological graph theory as in [WB78]. By the famous theorem of Brahana [Br23], any compact article no. 0069 105

📜 SIMILAR VOLUMES

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 the geodetic number of a graph
On the geodetic number of a graph
✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB
On the Interval Number of a Triangulated
On the Interval Number of a Triangulated Graph
✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect

On the interval number of a chordal grap
On the interval number of a chordal graph
✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum