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

Daniel Gonçalves
Algorithmes, Graphes et Combinatoire
CV

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

Domains

Discrete Mathematics [cs.DM]
Fichier principal
Vignette du fichier
533.pdf (351.82 Ko) Télécharger le fichier

Daniel Goncalves  : Connect in order to contact the contributor

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

Submitted on : Friday, November 13, 2020-11:43:10 AM

Last modification on : Friday, March 24, 2023-2:53:19 PM

Long-term archiving on : Sunday, February 14, 2021-6:41:17 PM

Download

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER ANR
60 View
137 Download

Altmetric

Share

More