The Turing Test for Graph Drawing Algorithms

Helen C. Purchase; Daniel Archambault; Stephen Kobourov; Martin Nöllenburg; Sergey Pupyrev; Hsiang Yun Wu

doi:10.1007/978-3-030-68766-3_36

The Turing Test for Graph Drawing Algorithms

Helen C. Purchase, Daniel Archambault, Stephen Kobourov, Martin Nöllenburg, Sergey Pupyrev, Hsiang Yun Wu

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on ‘small’ graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm.

Original language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers
Editors	David Auber, Pavel Valtr
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	466-481
Number of pages	16
ISBN (Print)	9783030687656
DOIs	https://doi.org/10.1007/978-3-030-68766-3_36
State	Published - 2020
Event	28th International Symposium on Graph Drawing and Network Visualization, GD 2020 - Virtual, Online Duration: Sep 16 2020 → Sep 18 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12590 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Symposium on Graph Drawing and Network Visualization, GD 2020
City	Virtual, Online
Period	9/16/20 → 9/18/20

Keywords

Empirical studies
Graph drawing algorithms
Turing test

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-68766-3_36

Cite this

Purchase, H. C., Archambault, D., Kobourov, S., Nöllenburg, M., Pupyrev, S., & Wu, H. Y. (2020). The Turing Test for Graph Drawing Algorithms. In D. Auber, & P. Valtr (Eds.), Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers (pp. 466-481). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12590 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-68766-3_36

The Turing Test for Graph Drawing Algorithms. / Purchase, Helen C.; Archambault, Daniel; Kobourov, Stephen et al.
Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers. ed. / David Auber; Pavel Valtr. Springer Science and Business Media Deutschland GmbH, 2020. p. 466-481 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12590 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Purchase, HC, Archambault, D, Kobourov, S, Nöllenburg, M, Pupyrev, S & Wu, HY 2020, The Turing Test for Graph Drawing Algorithms. in D Auber & P Valtr (eds), Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12590 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 466-481, 28th International Symposium on Graph Drawing and Network Visualization, GD 2020, Virtual, Online, 9/16/20. https://doi.org/10.1007/978-3-030-68766-3_36

Purchase HC, Archambault D, Kobourov S, Nöllenburg M, Pupyrev S, Wu HY. The Turing Test for Graph Drawing Algorithms. In Auber D, Valtr P, editors, Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2020. p. 466-481. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-68766-3_36

Purchase, Helen C. ; Archambault, Daniel ; Kobourov, Stephen et al. / The Turing Test for Graph Drawing Algorithms. Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers. editor / David Auber ; Pavel Valtr. Springer Science and Business Media Deutschland GmbH, 2020. pp. 466-481 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3e0b566363094bdc8c8daa0c7776eb6b,

title = "The Turing Test for Graph Drawing Algorithms",

abstract = "Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on {\textquoteleft}small{\textquoteright} graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm.",

keywords = "Empirical studies, Graph drawing algorithms, Turing test",

author = "Purchase, {Helen C.} and Daniel Archambault and Stephen Kobourov and Martin N{\"o}llenburg and Sergey Pupyrev and Wu, {Hsiang Yun}",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 28th International Symposium on Graph Drawing and Network Visualization, GD 2020 ; Conference date: 16-09-2020 Through 18-09-2020",

year = "2020",

doi = "10.1007/978-3-030-68766-3_36",

language = "English (US)",

isbn = "9783030687656",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "466--481",

editor = "David Auber and Pavel Valtr",

booktitle = "Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - The Turing Test for Graph Drawing Algorithms

AU - Purchase, Helen C.

AU - Archambault, Daniel

AU - Kobourov, Stephen

AU - Nöllenburg, Martin

AU - Pupyrev, Sergey

AU - Wu, Hsiang Yun

PY - 2020

Y1 - 2020

N2 - Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on ‘small’ graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm.

AB - Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on ‘small’ graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm.

KW - Empirical studies

KW - Graph drawing algorithms

KW - Turing test

UR - http://www.scopus.com/inward/record.url?scp=85102732887&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85102732887&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-68766-3_36

DO - 10.1007/978-3-030-68766-3_36

M3 - Conference contribution

AN - SCOPUS:85102732887

SN - 9783030687656

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 466

EP - 481

BT - Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers

A2 - Auber, David

A2 - Valtr, Pavel

PB - Springer Science and Business Media Deutschland GmbH

T2 - 28th International Symposium on Graph Drawing and Network Visualization, GD 2020

Y2 - 16 September 2020 through 18 September 2020

ER -

The Turing Test for Graph Drawing Algorithms

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this