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

Jérémie Chalopin; Daniel Gonçalves

Retour

Acte de colloque

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

Jérémie Chalopin et Daniel Gonçalves

STOC '09: 41st ACM Symposium on Theory of Computing, pp.631-638

STOC '09: 41st ACM Symposium on Theory of Computing (France, 31/05/2009–02/06/2009)

2009

Résumé

intersection graphs

planar graphs

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.

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: Every Planar Graph is the Intersection Graph of Segments in the Plane: Extended Abstract
Créateurs - sans rôle: Jérémie Chalopin - Laboratoire d’Informatique Fondamentale de Marseille
Daniel Gonçalves - Algorithmes, Graphes et Combinatoire
Détails de publication: STOC '09: 41st ACM Symposium on Theory of Computing, pp.631-638
Colloque: STOC '09: 41st ACM Symposium on Theory of Computing (France, 31/05/2009–02/06/2009)
Identifiants: 9944118009311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-00395364