Planar Graphs Have 1-string Representations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete and Computational Geometry Year : 2010

Planar Graphs Have 1-string Representations

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

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More