Planar Graphs as Intersection Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

Planar Graphs as Intersection Graphs

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.
No file

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00808045 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More