Skip to main content

Research Repository

Advanced Search

Minimising line segments in linear diagrams is NP-hard

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


Huang Hao Chen


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.

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
Keywords Linear diagrams, Complexity, Set-based visualisation
Public URL


You might also like

Downloadable Citations