Not all planar graphs are in PURE-4-DIR - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Graph Algorithms and Applications Year : 2020

Not all planar graphs are in PURE-4-DIR

Abstract

We prove that some planar graphs are not intersection graphs of segments if only four slopes are allowed for the segments, and if parallel segments do not intersect. This refutes a conjecture of D. West [D. West, SIAM J. Discrete Math. Newsletter, 1991].
Fichier principal
Vignette du fichier
533.pdf (351.82 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-03003499 , version 1 (13-11-2020)

Identifiers

Cite

Daniel Gonçalves. Not all planar graphs are in PURE-4-DIR. Journal of Graph Algorithms and Applications, 2020, 24 (3), pp.293-301. ⟨10.7155/jgaa.00533⟩. ⟨lirmm-03003499⟩
62 View
138 Download

Altmetric

Share

More