Minimising line segments in linear diagrams is NP-hard
Peter Chapman, Kevin Sim, Huang Hao Chen · Journal of Computer Languages · 2022
Linear diagrams have been shown to be an effective method of representing set-based data. Moreover, a number of guidelines have been proven to improve the efficacy of linear diagrams. One of these guidelines is to minimise the number of line segments appearing in a diagram. We show this problem to be NP-hard.