Planar Graphs Have 1-string Representations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete and Computational Geometry Année : 2010

Planar Graphs Have 1-string Representations

Jérémie Chalopin
Laboratoire d'informatique Fondamentale de Marseille - UMR 6166
Daniel Gonçalves
Algorithmes, Graphes et Combinatoire
CV
Pascal Ochem
Laboratoire de Recherche en Informatique
CV

Résumé

We prove that every planar graph is an intersection graph of strings in the plane such that any two strings intersect at most once.

Mots clés

Planar graphs Strings

Domaines

Combinatoire [math.CO]

Daniel Gonçalves  : Connectez-vous pour contacter le contributeur

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

Soumis le : mercredi 18 novembre 2009-10:34:47

Dernière modification le : lundi 15 avril 2024-18:14:03

Consulter le texte intégral

Dates et versions

lirmm-00433091 , version 1 (18-11-2009)

Identifiants

Citer

Jérémie Chalopin, Daniel Gonçalves, Pascal Ochem. Planar Graphs Have 1-string Representations. Discrete and Computational Geometry, 2010, 43 ((3)), pp.626-647. ⟨10.1007/s00454-009-9196-9⟩. ⟨lirmm-00433091⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

EC-PARIS LIF CNRS UNIV-AMU UMR8623 ALGCO LIRMM UNIV-PARIS-SACLAY MIPS UNIV-MONTPELLIER LIS-LAB
178 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More