Minimising line segments in linear diagrams is NP-hard

被引：2

作者：

Chapman, Peter ^{[1
]}

Sim, Kevin ^{[1
]}

Chen, Huang Hao ^{[1
]}

机构：

[1] Edinburgh Napier Univ, Sch Comp, Edinburgh, Scotland

来源：

JOURNAL OF COMPUTER LANGUAGES | 2022年 / 71卷

关键词：

Linear diagrams; Complexity; Set-based visualisation;

D O I：

10.1016/j.cola.2022.101136

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页数：4

共 27 条

[1] The Perception of Clutter in Linear Diagrams [J].

Alqadah, Mohanad ;

Stapleton, Gem ;

Howse, John ;

Chapman, Peter .

DIAGRAMMATIC REPRESENTATION AND INFERENCE, DIAGRAMS 2016, 2016, 9781 :250-257

[2]

Alqadah M, 2014, LECT NOTES COMPUT SC, V8578, P108, DOI 10.1007/978-3-662-44043-8_15

[3]

Alqadah Mohanad, 2016, SETVR DIAGRAMS, P4

[4]

[Anonymous], 2003, DESCRIPTION LOGIC HD

[5]

[Anonymous], 2010, VAMOS

[6]

Benjamins VRichard., 2005, Law and the semantic web: legal ontologies, methodologies, legal information retrieval, and applications, V3369

[7] Evaluation of Traditional, Orthogonal, and Radial Tree Diagrams by an Eye Tracking Study [J].

Burch, Michael ;

Heinrich, Julian ;

Konevtsova, Natalia ;

Hoeferlin, Markus ;

Weiskopf, Daniel .

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 2011, 17 (12) :2440-2448

[8] Minimising the number of gap-zeros in binary matrices [J].

Chakhlevitch, Konstantin ;

Glass, Celia A. ;

Shakhlevich, Natalia V. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 229 (01) :48-58

[9] Interactivity in Linear Diagrams [J].

Chapman, Peter .

DIAGRAMMATIC REPRESENTATION AND INFERENCE, DIAGRAMS 2021, 2021, 12909 :449-465

[10] PaL diagrams: A linear diagram-based visual language [J].

Chapman, Peter ;

Stapleton, Gem ;

Rodgers, Peter .

JOURNAL OF VISUAL LANGUAGES AND COMPUTING, 2014, 25 (06) :945-954

← 1 2 3 →