Not all planar graphs are in PURE-4-DIR
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]
Loading...