Planar Graphs as L-intersection or L-contact graphs

Daniel Gonçalves 1 Lucas Isenmann 1 Claire Pennarun 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The ⌞-intersection graphs are the graphs that have a representation as intersection graphs of axis-parallel ⌞ shapes in the plane. A subfamily of these graphs are {⌞, |, –}-contact graphs which are the contact graphs of axis parallel ⌞, |, and – shapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are ⌞-intersection graphs, and that triangle-free planar graphs are {⌞, |, –}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01738150
Contributor : Daniel Gonçalves <>
Submitted on : Tuesday, March 20, 2018 - 11:36:28 AM
Last modification on : Wednesday, June 19, 2019 - 3:37:37 PM

Links full text

Identifiers

Collections

Citation

Daniel Gonçalves, Lucas Isenmann, Claire Pennarun. Planar Graphs as L-intersection or L-contact graphs. SODA: Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. pp.172-184, ⟨10.1137/1.9781611975031.12⟩. ⟨lirmm-01738150⟩

Share

Metrics

Record views

119