Tel-Aviv University - Computer Science Colloquium
Sunday, April 25, 14:15-15:15
at 14:00 The crossing number of a graph G, denoted by cr(G), is the smallest number of edge crossings in any drawing of G in the plane. Clearly, cr(G)=0 if and only if G is planar. Garey and Johnson proved that the determination of cr(G) is an NP-complete problem. In the past twenty years, it turned out that crossing numbers play an important role in various fields of discrete and computational geometry, and they can also be used, e.g.,to obtain lower bounds on the chip area required for the VLSI circuit layout of a graph. In this lecture, first we recall two important general lower bounds for crossing numbers and outline some of their applications. Next we describe some recent extensions and generalizations of these results. We also introduce three alternative notions of crossing number, analyze their relationship, and state some tantalizing open problems.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html