Minimising line segments in linear diagrams is NP-hard

Chapman, Peter; Sim, Kevin; Hao Chen, Huang

Abstract

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.

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

• Journal Article Type: Article
• Acceptance Date: Jul 8, 2022
• Online Publication Date: Jul 18, 2022
• Publication Date: 2022-08
• Deposit Date: Aug 9, 2022
• Publicly Available Date: Aug 9, 2022
• Journal: Journal of Computer Languages
• Print ISSN: 2590-1184
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 71
• Article Number: 101136
• DOI: https://doi.org/10.1016/j.cola.2022.101136
• Keywords: Linear diagrams, Complexity, Set-based visualisation
• Public URL: http://researchrepository.napier.ac.uk/Output/2889810