Not all planar graphs are in PURE-4-DIR - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Journal of Graph Algorithms and Applications Année : 2020

Not all planar graphs are in PURE-4-DIR

Résumé

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 et versions

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

Identifiants

Citer

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⟩
65 Consultations
142 Téléchargements

Altmetric

Partager

More