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.

Domains

Combinatorics [math.CO]

Daniel Gonçalves  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00395364

Submitted on : Monday, June 15, 2009-2:58:43 PM

Last modification on : Friday, April 19, 2024-3:14:37 PM

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

LIF CNRS UNIV-AMU ALGCO LIRMM MIPS UNIV-MONTPELLIER LIS-LAB
253 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More