Every Planar Graph is the Intersection Graph of Segments in the Plane: Extended Abstract - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

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

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.
No file

Dates and versions

lirmm-00395364 , version 1 (15-06-2009)

Identifiers

  • HAL Id : lirmm-00395364 , version 1

Cite

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⟩
246 View
0 Download

Share

Gmail Facebook X LinkedIn More