Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395364
Contributor : Daniel Gonçalves <>
Submitted on : Monday, June 15, 2009 - 2:58:43 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Identifiers

  • HAL Id : lirmm-00395364, version 1

Collections

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. ⟨lirmm-00395364⟩

Share

Metrics

Record views

270