Crossing Numbers of Graphs

A graph consists of nodes and edges, and when it is drawn, some edges are likely to cross each other. The number of such crossing edges is known as the crossing number of a graph. This book examines various aspects of crossing numbers on a variety of graphs, including introductory results, drawings on various types of media, and the complexity of algorithms used for their computation.

 

The first part of the book is organized into four chapters. Chapter 1 introduces crossing numbers, proves some theorems on bounds, and discusses results on bipartite graphs and complete graphs. Chapter 2 begins with theorems on the number of good drawings and also gives the crossing number for the Cartesian product of two graphs. The discussion continues for graphs with cycles, hypercubes, and crossing critical graphs. Chapter 3 provides connections between crossing numbers and other graph properties such as bisection width and cutwidth. Similarly, properties such as skewness, edge crossing numbers, and thickness are presented. Further, the chapter details the crossing numbers for embedded graphs. Next, Chapter 4 explores algorithmic aspects of crossing number computations, showing that, generally, the complexity is NP for crossing number algorithms. The chapter also introduces methods for how to draw graphs.

 

The second part of the book is composed of the remaining eight chapters. Chapters 5 and 6 are on rectilinear crossing numbers. The rectilinear drawing of a graph is a drawing where its edges are drawn with straight lines. The related crossing number bounds, drawing structures, etc. are provided. Chapter 7 is on local crossing numbers: these are the largest number of crossings for any edge of a graph.  Their bounds, the rectilinear version of local crossing numbers, and the related planar coloring problem are discussed. Chapter 8 looks at crossing numbers of graphs drawn inside books, and string graphs and pair crossing numbers are studied in Chapter 9.  The next two chapters introduce crossing numbers of graphs drawn on more than one plane, odd crossing numbers, and algebraic crossing numbers.  Chapter 12 looks at maximum crossing numbers, which are defined to be the largest number of possible crossing edges over all the possible ways to draw a graph under some conditions. After giving theorems on polygons, and complete graphs, the chapter delves into various types of thrackles. 

 

To conclude, the book also has two appendices. The first appendix presents the basics of topological theory of graphs, and the second is on algorithm complexity. The book ends with more than 25 pages of bibliography.

 

A background in graph theory and algorithmic complexity theory is required to understand the book. However, exercises at the end of each chapter make it suitable to be used as a textbook.

---

 

Dr. Maulik A. Dave is an experienced reviewer of research papers, and books in computer science, mathematics, and engineering. Email: maulikadave@aim.com.