Back to Search Start Over

Every planar graph is the intersection graph of segments in the plane

Authors :
Jérémie Chalopin
Daniel Gonçalves
Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF)
Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS)
Algorithmes, Graphes et Combinatoire (ALGCO)
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
Source :
STOC, STOC '09: 41st ACM Symposium on Theory of Computing, STOC '09: 41st ACM Symposium on Theory of Computing, May 2009, France. pp.631-638
Publication Year :
2009
Publisher :
ACM, 2009.

Abstract

International audience; Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton\nUniversity, 1984) that every planar graph is the intersection graph of some segments in the plane.

Details

Database :
OpenAIRE
Journal :
Proceedings of the forty-first annual ACM symposium on Theory of computing
Accession number :
edsair.doi.dedup.....94c8e3455fd59a4c72d2a3c082693617
Full Text :
https://doi.org/10.1145/1536414.1536500