Skip to Main content Skip to Navigation
Conference papers

Planar Graphs as Intersection Graphs

Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Daniel Gonçalves <>
Submitted on : Thursday, April 4, 2013 - 5:33:48 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM


  • HAL Id : lirmm-00808045, version 1



Daniel Gonçalves. Planar Graphs as Intersection Graphs. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. ⟨lirmm-00808045⟩



Record views