Planar graphs as L-intersection or L-contact graphs
| Autor: | Lucas Isenmann, Claire Pennarun, Daniel Gonçalves |
|---|---|
| Přispěvatelé: | Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-16-CE40-0009,GATO,Graphes, Algorithmes et TOpologie(2016) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Plane (geometry) 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Computer Science::Computational Geometry [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Planar graph Combinatorics symbols.namesake Intersection 010201 computation theory & mathematics Simple (abstract algebra) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0202 electrical engineering electronic engineering information engineering symbols Computer Science - Computational Geometry 020201 artificial intelligence & image processing Representation (mathematics) Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | SODA 29th Annual ACM-SIAM Symposium on Discrete Algorithms SODA: Symposium on Discrete Algorithms SODA: Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. pp.172-184, ⟨10.1137/1.9781611975031.12⟩ |
| DOI: | 10.1137/1.9781611975031.12⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|