The structure of edge crossings in graph layouts plays important roles in information visualization, network theory, and chip design. The emerging theory has found many applications in computer science, topological graph theory, incidence geometry, additive number theory, and elsewhere. In the process, powerful techniques have been developed to deal with problems of this kind. In this talk, I will present a number of simply formulated notoriously difficult open problems and I will indicate the most effective known ideas on how to attack them.

In particular, I will discuss the following question. A graph drawn in the plane is called r-quasiplanar if it has no r pairwise crossing edges. Does there exist a constant c=c(r) such that every r-quasiplanar graph of n vertices has at most cn edges? For r<5, the answer is yes, but for larger values the problem is open. I will explain why the problem is related to the theory of perfect graphs proposed by Claude Berge, who passed away 20 years ago. This talk is dedicated to his memory.