Every Planar Graph is the Intersection Graph of Segments in the Plane: Extended Abstract

Jérémie Chalopin 1 Daniel Gonçalves 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Communication dans un congrès
STOC '09: 41st ACM Symposium on Theory of Computing, May 2009, France. pp.631-638, 2009, 〈http://www.umiacs.umd.edu/conferences/stoc2009/index.shtml〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395364
Contributeur : Daniel Gonçalves <>
Soumis le : lundi 15 juin 2009 - 14:58:43
Dernière modification le : vendredi 9 mars 2018 - 11:26:00

Identifiants

  • HAL Id : lirmm-00395364, version 1

Citation

Jérémie Chalopin, Daniel Gonçalves. Every Planar Graph is the Intersection Graph of Segments in the Plane: Extended Abstract. STOC '09: 41st ACM Symposium on Theory of Computing, May 2009, France. pp.631-638, 2009, 〈http://www.umiacs.umd.edu/conferences/stoc2009/index.shtml〉. 〈lirmm-00395364〉

Partager

Métriques

Consultations de la notice

154