Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract: Crossing number is the standard measure of nonplanarity of graphs. It appears naturally in the aesthetic drawing of graph-like structures and in the design of integrated circuits and printed circuit boards. Very little is known on exact values of crossing numbers for explicitely given graphs. The problem is NP-complete and there exists a polylogarithmic approximation algorithm for finding crossing numbers. We survey some basic results on crossing numbers and then describe several lower bound methods which are related to graph parameters like bisection width, edge forwarding index and cutwidth.