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.
Type de document :
Communication dans un congrès
LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. VI Latin-American Algorithms, Graphs and Optimization Symposium, 2011, 〈http://www-2.dc.uba.ar/lagos2011/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00808045
Contributeur : Daniel Gonçalves <>
Soumis le : jeudi 4 avril 2013 - 17:33:48
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00808045, version 1

Collections

Citation

Daniel Gonçalves. Planar Graphs as Intersection Graphs. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. VI Latin-American Algorithms, Graphs and Optimization Symposium, 2011, 〈http://www-2.dc.uba.ar/lagos2011/〉. 〈lirmm-00808045〉

Partager

Métriques

Consultations de la notice

66