Skip to content

Read-only version: For security reasons, the Research Information System (FIS) has been temporarily replaced by this read-only version. All public content and full texts remain available; login, editing, submission and statistics are not available. Questions: fis@uni-bamberg.de

Home › Publications › GraphTrials : Visual Proofs of Graph Properties

Publication

GraphTrials : Visual Proofs of Graph Properties

Förster, Henry; Klesen, Felix; Dwyer, Tim; u. a. (2026): GraphTrials : Visual Proofs of Graph Properties, in: Bamberg: Otto-Friedrich-Universität, S. 8767–8781.

Details

Faculty/Chair
Faculty/Professorship
Author
Förster, Henry; Klesen, Felix; Dwyer, Tim; Eades, Peter; Hong, Seok-Hee; Kobourov, Stephen; Liotta, Giuseppe; Misue, Kazuo; Montecchiani, Fabrizio; ORCID iDPastukhov, Alexander; Schreiber, Falk
Publisher Information
Otto-Friedrich-Universität : Bamberg
Year of publication
2026
Source/Other editions
IEEE transactions on visualization and computer graphics : TVCG, New York, NY: Institute of Electrical and Electronics Engineers (IEEE), 2025, Jg. 31, Nr. 10, S. 8767–8781, ISSN: 1077-2626
Year of first publication
2025
Language
English
Licence
URN
Abstract

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 questionanswering tools, issues of trustworthiness and explainability of generated answers motivate a significant new role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion (e. g., from an AI) 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. Then, we provide further examples of visual certificates for problems in different visual proof complexity classes. Finally, we conclude the paper with a discussion of the limitations of our model and some open problems.

Keywords
-
DDC Classification
150 Psychology
RVK Classification
CP 9500
Type
Article
URI
Activation date
2026-08-19

Permalink: https://fis.uni-bamberg.de/handle/uniba/116874 · Data as JSON · Cite: BibTeX · RIS

Data as of: 2026-11-16

Restricted read-only access: login, editing and submission are temporarily disabled.