Intersection Graphs

3-coloring arrangements of line segments with 4 slopes is hard

In a paper first appeared at [SODA ’04](https://dl.acm.org/doi/10.5555/982792.982921), Eppstein proved that testing the $3$-colorability of arrangements of line segments is an NP-complete problem. However, if the slopes of the segments are limited to …