Skip to Main content Skip to Navigation
Journal articles

Not all planar graphs are in PURE-4-DIR

Daniel Gonçalves 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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].
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03003499
Contributor : Daniel Goncalves <>
Submitted on : Friday, November 13, 2020 - 11:43:10 AM
Last modification on : Monday, December 14, 2020 - 5:26:20 PM
Long-term archiving on: : Sunday, February 14, 2021 - 6:41:17 PM

File

Identifiers

Collections

Citation

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

Share

Metrics

Record views

70

Files downloads

73