Article Dans Une Revue Journal of Graph Algorithms and Applications Année : 2020

Not all planar graphs are in PURE-4-DIR

Daniel Gonçalves
ALGCO - Algorithmes, Graphes et Combinatoire
CV

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].

Domaines

Connectez-vous pour contacter le contributeur

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

Soumis le : vendredi 13 novembre 2020-11:43:10

Dernière modification le : vendredi 21 novembre 2025-08:43:53

Archivage à long terme le : dimanche 14 février 2021-18:41:17

Consulter le texte intégral

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⟩

Exporter

Collections

166 Consultations
149 Téléchargements

Altmetric

Partager

  • More