Planar Graphs as Intersection Graphs
Résumé
Given a set P of geometric objects in the plane, the intersection graph of P is the graph with vertex set P and which edges are defined by the intersections of the objects. By restricting the geometric objects allowed in P, those geometric models define a great variety of graph classes, like interval graphs, circle graphs or disk graphs. During this talk we will see that planar graphs can be represented by many intersection models, and that some of those models characterize them. An example of such characterization is Koebe's Theorem that every planar graph is the intersection graph of touching discs in the plane, and vice-versa. We will also see how some of these geometric models of planar graphs are related to special orientations of those graphs (orientations with bounded out-degree). Finally, we will review few results where the geometric objects lie in other surfaces or in the 3-dimensional space.