Not all planar graphs are in PURE-4-DIR

Daniel Gonçalves

doi:10.7155/jgaa.00533

Back

Journal article

Open access

Peer reviewed

Not all planar graphs are in PURE-4-DIR

Daniel Gonçalves

Journal of Graph Algorithms and Applications, Vol.24(3), pp.293-301

06/2020

DOI: https://doi.org/10.7155/jgaa.00533

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

Files and links (2)

url

Find in HALView

url

https://doi.org/10.7155/jgaa.00533View

Published (Version of record) Open

Metrics

1 Record Views

Details

Title: Not all planar graphs are in PURE-4-DIR
Creators - without role: Daniel Gonçalves - Algorithmes, Graphes et Combinatoire
Publication Details: Journal of Graph Algorithms and Applications, Vol.24(3), pp.293-301
Identifiers: 9941499609311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: lirmm-03003499