Planar Graphs Have 1-string Representations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete and Computational Geometry Year : 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

Abstract

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

Keywords

Planar graphs Strings

Domains

Combinatorics [math.CO]

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

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

Submitted on : Wednesday, November 18, 2009-10:34:47 AM

Last modification on : Monday, April 15, 2024-6:14:03 PM

Consult the full text

Dates and versions

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

Identifiers

Cite

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⟩

Export

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
205 View
0 Download

Altmetric

Share

More