Part 3. Planar graphs and minimum crossing number

The final part of this book has a single data structure as its main thread: graphs. They will be used, however, more as a touchstone to compare different techniques throughout chapters whose main focus will be on optimization algorithms.

We won’t delve into the basics of graphs, but we still start this part with a brief introduction to their basic concepts and a few cornerstone algorithms to traverse graphs.

These are necessary to describe an interesting, often neglected problem that has broad application in our industry: displaying graphs in the two-dimensional plane. This is a difficult problem that can’t be solved efficiently on classical computers. Nevertheless, it’s one for which approximate solutions are often enough, and this gives us a good reason to introduce optimization algorithms, the real star of part 3.

The final chapters of this book will describe three optimization techniques that are widely used to tackle optimization problems and drive today’s AI and big data effort: gradient descent, simulated annealing, and genetic algorithms.

Chapter 14 is a short introduction to graphs, condensing the basics of this fundamental data structure needed to understand part 3. It also illustrates DFS, BFS, Dijkstra’s, and A* algorithms, and describes how to use them to solve the “minimum-distance path” problem.