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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

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
Title of host publication	Graph Drawing and Network Visualization - 28th International Symposium, GD 2020 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123
Editors	David Auber, Pavel Valtr
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	466-481
Number of pages	16
ISBN (Electronic)	9783030687663
ISBN (Print)	9783030687656
DOIs	https://doi.org/10.1007/978-3-030-68766-3_36
Publication status	Published - 2020
Externally published	Yes
Event	Graph Drawing 2020 - Online, Canada Duration: 16 Sept 2020 → 18 Sept 2020 Conference number: 28th https://link.springer.com/book/10.1007/978-3-030-68766-3 (Proceedings) https://gd2020.cs.ubc.ca/ (Website)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12590
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Graph Drawing 2020
Abbreviated title	GD 2020
Country/Territory	Canada
Period	16/09/20 → 18/09/20
Internet address	https://link.springer.com/book/10.1007/978-3-030-68766-3 (Proceedings) https://gd2020.cs.ubc.ca/ (Website)

Keywords

Empirical studies
Graph drawing algorithms
Turing test

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 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123 (pp. 466-481). (Lecture Notes in Computer Science; Vol. 12590). Springer. https://doi.org/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 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123. editor / David Auber ; Pavel Valtr. Cham Switzerland : Springer, 2020. pp. 466-481 (Lecture Notes in Computer Science).

@inproceedings{cf9289243d9746ecaed672fafc4c2a07,

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 Hsiang-Yun Wu",

note = "Funding Information: Acknowledgement. We are grateful to all the experimental participants, to Drew Sheets who assisted with creating the graphs in yEd, and to John Hamer who implemented the online experimental system. Ethical approval was given by the University of Arizona Institutional Review Board (ref: 1712113015). This work is supported by NSF grants CCF-1740858, CCF-1712119, DMS-1839274, and FWF grant P 31119. Funding Information: We are grateful to all the experimental participants, to Drew Sheets who assisted with creating the graphs in yEd, and to John Hamer who implemented the online experimental system. Ethical approval was given by the University of Arizona Institutional Review Board (ref: 1712113015). This work is supported by NSF grants CCF-1740858, CCF-1712119, DMS-1839274, and FWF grant P 31119. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; Graph Drawing 2020, GD 2020 ; Conference date: 16-09-2020 Through 18-09-2020",

year = "2020",

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

language = "English",

isbn = "9783030687656",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "466--481",

editor = "David Auber and Pavel Valtr",

booktitle = "Graph Drawing and Network Visualization - 28th International Symposium, GD 2020 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123",

url = "https://link.springer.com/book/10.1007/978-3-030-68766-3, https://gd2020.cs.ubc.ca/",

}

Purchase, HC, 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 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123. Lecture Notes in Computer Science, vol. 12590, Springer, Cham Switzerland, pp. 466-481, Graph Drawing 2020, British Columbia, Canada, 16/09/20. 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 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123. ed. / David Auber; Pavel Valtr. Cham Switzerland: Springer, 2020. p. 466-481 (Lecture Notes in Computer Science; Vol. 12590).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

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

N1 - Conference code: 28th

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

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

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

M3 - Conference Paper

AN - SCOPUS:85102732887

SN - 9783030687656

T3 - Lecture Notes in Computer Science

SP - 466

EP - 481

BT - Graph Drawing and Network Visualization - 28th International Symposium, GD 2020 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123

A2 - Auber, David

A2 - Valtr, Pavel

PB - Springer

CY - Cham Switzerland

T2 - Graph Drawing 2020

Y2 - 16 September 2020 through 18 September 2020

ER -

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 Vancouver, BC, Canada, September 16–18, 2020 Revised Selected Papers 123. Cham Switzerland: Springer. 2020. p. 466-481. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-68766-3_36

The turing test for graph drawing algorithms

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this