Planar Graphs as Intersection Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2011

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.
Fichier non déposé

Dates et versions

lirmm-00808045 , version 1 (04-04-2013)

Identifiants

  • HAL Id : lirmm-00808045 , version 1

Citer

Daniel Gonçalves. Planar Graphs as Intersection Graphs. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. ⟨lirmm-00808045⟩
236 Consultations
0 Téléchargements

Partager

More