GraphTrials: Visual Proofs of Graph Properties
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916381836967936 |
|---|---|
| author | Förster, Henry Klesen, Felix Dwyer, Tim Eades, Peter Hong, Seok-Hee Kobourov, Stephen G. Liotta, Giuseppe Misue, Kazuo Montecchiani, Fabrizio Pastukhov, Alexander Schreiber, Falk |
| author_facet | Förster, Henry Klesen, Felix Dwyer, Tim Eades, Peter Hong, Seok-Hee Kobourov, Stephen G. Liotta, Giuseppe Misue, Kazuo Montecchiani, Fabrizio Pastukhov, Alexander Schreiber, Falk |
| contents | Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer's perception, in particular, pre-attentive processing (e.g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02907 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | GraphTrials: Visual Proofs of Graph Properties Förster, Henry Klesen, Felix Dwyer, Tim Eades, Peter Hong, Seok-Hee Kobourov, Stephen G. Liotta, Giuseppe Misue, Kazuo Montecchiani, Fabrizio Pastukhov, Alexander Schreiber, Falk Human-Computer Interaction Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer's perception, in particular, pre-attentive processing (e.g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes. |
| title | GraphTrials: Visual Proofs of Graph Properties |
| topic | Human-Computer Interaction |
| url | https://arxiv.org/abs/2409.02907 |