Minimising line segments in linear diagrams is NP-hard

Research Output

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.

Type:

Article
Date:

18 July 2022
Publication Status:

Published
DOI:

10.1016/j.cola.2022.101136
Cross Ref:

10.1016/j.cola.2022.101136
ISSN:

2590-1184
Funders:

Edinburgh Napier Funded

http://researchrepository.napier.ac.uk/output/2889810 Chapman, P., Sim, K., & Hao Chen, H. (2022). Minimising line segments in linear diagrams is NP-hard. Journal of Computer Languages, 71, Article 101136. https://doi.org/10.1016/j.cola.2022.101136

Citation

Chapman, P., Sim, K., & Hao Chen, H. (2022). Minimising line segments in linear diagrams is NP-hard. Journal of Computer Languages, 71, Article 101136. https://doi.org/10.1016/j.cola.2022.101136