---
# title: "Benchmark Datasets for Graph Layout Algorithms"
title: "GLaDOS: Graph Layout algorithm Datasets for Open Science"
number-sections: true
self-contained: false
author:
  - name: Sara Di Bartolomeo
    orcid: 0000-0001-9517-3526
    email: dibartolomeo.sara@gmail.com
    affiliations:
      - name: University of Konstanz
        city: Konstanz
        country: Germany
      - name: TU Wien
        city: Vienna
        country: Austria
  - name: Connor Wilson
    orcid: 0000-0002-6936-4078
    email: wilson.conn@northeastern.edu
    affiliations:
      - name: Northeastern University
        city: Boston
        state: MA
        country: USA
  - name: Eduardo Puerta
    orcid: 0000-0003-4664-4365
    email: puerta.e@northeastern.edu
    affiliations:
      - name: Northeastern University
        city: Boston
        state: MA
        country: USA
  - name: Tarik Crnovrsanin
    orcid: 0000-0002-4397-5532
    email: t.crnovrsanin@northeastern.edu
    affiliations:
      - name: Northeastern University
        city: Boston
        state: MA
        country: USA
  - name: Alexander Frings
    orcid: 0009-0009-1718-2967
    email: alexander.frings@uni-konstanz.de
    affiliations:
      - name: University of Konstanz
        city: Konstanz
        country: Germany
  - name: Cody Dunne
    orcid: 0000-0002-1609-9776
    email: c.dunne@northeastern.edu
    affiliations:
      - name: Northeastern University
        city: Boston
        state: MA
        country: USA

---

<!-- ::: {.callout-important appearance="simple"}
## Under Review {.unnumbered}
This paper is [under review](https://www.journalovi.org/under-review.html) on the experimental track of
the [Journal of Visualization and Interaction](https://www.journalovi.org/). See the 
[reviewing process](https://github.com/journalovi/2024-dibartolomeo-gd-benchmark/issues).
::: -->


::: {.callout-note appearance="simple" icon="false" collapse="false"}

## Abstract {.unnumbered}

<link rel="stylesheet" href="style/style.css"></link>
<script src="js/collapsible_info.js"></script>

```{ojs}
//| echo: false
//| output: false 
Plot = import("https://esm.run/@observablehq/plot")
```

### Introduction

Computational evaluations are crucial for standardized and objective evaluation of graph layout algorithms. Standard
benchmark datasets facilitate comparison with prior work, and reliable access to datasets is fundamental for
replicability. However, there is no comprehensive repository of benchmark datasets for Graph Drawing, and many datasets have been lost.

### Data collection

We collected 196 papers from Graph Drawing, IEEE venues, and Eurographics venues that include computational evaluations
of graph layout algorithms. We searched for the datasets used.

### Data analysis

We archived datasets we found and re-created ones that were lost but had sufficient replication instructions. We
classified graphs by their features and statistics. We also found text and images from papers using those graphs.

### Implementation

We implemented graph creation, data analysis, and website code.

### Materials

We provide a [Graph Layout Benchmark Datasets](https://visdunneright.github.io/gd_benchmark_sets/) website and a [long-term archive](https://osf.io/j7ucv/) which includes the documentation, code, and data for the website, benchmark datasets, analysis code, graph conversion code, and this paper.

### Conclusion

We provide a resource for the Graph Drawing and visualization communities to use to find datasets for computational
evaluations of graph layout algorithms. Our organization by features and statistics supports rapid identification of
relevant graphs. We have re-created and archived graphs used in research for their long-term preservation.
:::

<!-- We can't get rid of the `Note 1: ` prefix if there are any cross-references to the note, and cross-references to sections in the note don't work if it is collapsed. -->
::: {#nte-post-abstract .callout-note appearance="simple" icon="false" collapse="true"}

## Materials, Authorship, Acknowledgements, License, Conflicts

###### Research materials 

The supplemental material for this publication includes:

* The [Graph Benchmark Datasets](https://visdunneright.github.io/gd_benchmark_sets/) website, hosted on GitHub Pages.
* A main project on OSF which contains PDFs of our publications and the benchmark datsets in several common graph file formats, archived for long-term availability: <https://osf.io/j7ucv/>.
* An OSF component which contains the website code and survey data: <https://osf.io/q4697/> ([github.com/visdunneright/gd_benchmark_sets/](https://github.com/visdunneright/gd_benchmark_sets/))
* ... graph data, graph format conversion code, and analysis code: <https://osf.io/j2tfs/> ([github.com/VisDunneRight/benchmark_sets_analysis_data/](https://github.com/VisDunneRight/benchmark_sets_analysis_data/))
* ... this publication's code: <https://osf.io/qx3zh/> ([github.com/VisDunneRight/jovi-benchmark-sets](https://github.com/VisDunneRight/jovi-benchmark-sets)).
* The original database used for metadata collection and storage is available on Notion as [Benchmark datasets](https://picorana.notion.site/64e0439269f9497799025562a4087ce1?v=271e88e50ca24ee0bfd1c99ffa25daf5&pvs=74).

Archives of these connected GitHub repositories will be added to OSF storage upon paper acceptance.

###### Authorship

* **Sara Di Bartolomeo** <a href="https://orcid.org/0000-0001-9517-3526"><img src="images/ORCID_iD.svg.png" alt="orcid_16x16@2.gif" width="20"/></a> : Conceptualization, Data Collection & Categorization & Curation, Writing - Original Draft + Review & Editing, Visualization, Validation.
* **Connor Wilson** <a href="https://orcid.org/0000-0002-6936-4078"><img src="images/ORCID_iD.svg.png" alt="orcid_16x16@2.gif" width="20"/></a> : Data Collection & Categorization & Curation, Writing - Original Draft + Review & Editing, Validation.
* **Eduardo Puerta** <a href="https://orcid.org/0000-0003-4664-4365"><img src="images/ORCID_iD.svg.png" alt="orcid_16x16@2.gif" width="20"/></a> : Data Collection & Categorization & Curation, Writing - Original Draft + Review & Editing, Validation.
* **Tarik Crnovrsanin** <a href="https://orcid.org/0000-0002-4397-5532"><img src="images/ORCID_iD.svg.png" alt="orcid_16x16@2.gif" width="20"/></a> : Data Collection & Categorization & Curation, Writing - Original Draft + Review & Editing, Validation.
* **Alexander Frings** <a href="https://orcid.org/0009-0009-1718-2967"><img src="images/ORCID_iD.svg.png" alt="orcid_16x16@2.gif" width="20"/></a> : Data Categorization & Curation, Writing - Review & Editing, Software, Visualization, Validation.
* **Cody Dunne** <a href="https://orcid.org/0000-0002-1609-9776"><img src="images/ORCID_iD.svg.png" alt="orcid_16x16@2.gif" width="20"/></a> : Supervision, Writing - Original Draft + Review & Editing, Validation, Funding Acquisition.

###### Acknowledgements

This work was supported by the U.S. National Science Foundation (NSF) under award number CAREER IIS-2145382 and the Austrian Science Fund (FWF) [ESP 513-N].

###### License

All text, data, and documentation are licensed under a [Creative Commons Attribution 4.0 International License](https://creativecommons.org/licenses/by/4.0/).
All code is released under the [Apache 2.0 License](https://opensource.org/license/apache-2-0).

###### Conflicts of interest

The authors declare that there are no competing interests.
:::

# Introduction

Benchmarking is a crucial aspect of computer science, as it allows researchers, developers, and engineers to compare the
performance of various systems, algorithms, or hardware. A benchmark is a standardized test or set of tests used to
measure and compare the performance of hardware, software, or systems under specific conditions. Benchmarking aims to
provide objective and consistent metrics that allow for fair comparisons and informed decision-making. Benchmarks are
widely used in various fields, including computer hardware evaluation, software optimization, and system performance
analysis.
In all these fields, benchmarking provides a standardized and objective way to compare and assess the performance of
different systems, algorithms, or software implementations. It aids in making informed decisions about which solution
best suits a specific use case or requirement.

The same is true for graph drawing, particularly for studying the performance and results of graph layout
algorithms [@dibartolomeo2024evaluating].
Benchmark datasets can provide a standardized set of graphs with known properties and characteristics.
These graphs can vary in size, density, connectivity, and structure.
Having reference collections of benchmark graphs is a huge positive for these evaluations: indeed, if algorithms are tested on the same easy-to-find datasets, it becomes easier to compare them and benefits the reproducibility of the experiment.
Researchers can objectively compare their performance or the quality of their results by applying various graph layout
algorithms to the same benchmark dataset.

In our own work, we have faced challenges in determining which benchmark datasets to use for evaluating the layout
algorithms we developed. This led us to build a collection of benchmark datasets used in previous graph layout algorithm
papers and a [Graph Benchmark Datasets](https://visdunneright.github.io/gd_benchmark_sets/) website for perusing the
collection. We collected 196 papers from Graph Drawing, IEEE venues, and Eurographics venues that include computational
evaluations of graph layout algorithms. We then searched for the datasets used for the benchmarks. We collected the data
we could find and had permission to archive and re-created datasets that were lost but had sufficient replication
instructions. We classified graphs by their features and statistics. We also found text and images from papers using
those graphs.

This paper aims to present this graph drawing benchmark sets resource to the Graph Drawing and visualization communities
so that other authors may benefit from our archiving and organization efforts. We hope this resource will encourage the
discoverability of these datasets and the ease of running benchmarks for graph layout algorithms. Moreover, as reliable
access to datasets is fundamental for replicability, we aim to preserve these datasets in perpetuity. Beyond collecting
available datasets and re-creating lost ones, we archived all our materials [on OSF](https://osf.io/j7ucv/) for
long-term availability. This included saving each graph in multiple common file formats to avoid translation issues for
individual authors. We believe our work will lead to more reproducible and replicable Graph Drawing research by
providing a long-term and open archive of the data we use in our computational evaluations.

Specifically, we contribute:

- A systematic collection of the graphs commonly used in Graph Drawing research---along with a characterization of the graph features available in each dataset---which will help future researchers and practitioners identify appropriate benchmark datasets to use for their evaluations. 
The work we did also includes reconstructing lost datasets based on author descriptions, or scouting through citations or emailing authors to hopefully find these lost collections.
- A website for perusing this collection, [available here](https://visdunneright.github.io/gd_benchmark_sets/).
- A long-term archive of our metadata and the collection to aid in reproducibility and replicability of evaluations.

Please see [our materials statement](#nte-post-abstract) above for our supplemental materials, including links to the website, code and data, OSF archive, and Notion database.

```{ojs}
//| echo: false
literature_pre = await FileAttachment("data/Literature.csv").csv()
benchmark_datasets_pre = await FileAttachment("data/Benchmark_datasets.csv").csv()
literature = literature_pre.filter(d => !d.Name.includes("EXCLUDE") && !d.Name == "")
benchmark_datasets = benchmark_datasets_pre.filter(l => l.Name != "" && l.Name != "Debates")
paper_sources_pre = await FileAttachment("data/Paper Sources.csv").csv()
paper_source = paper_sources_pre.filter(l => l.Name != "")
```

```{ojs}
//| echo: false
//| output: false
dict_of_graph_features_to_colors = {
  let all_graph_features = [... new Set(benchmark_datasets.map(a => a["graph features handled"].split(",").map(a => a.trim())).flat().filter(a => a != ""))]
  let d = {}
  let colorscheme = d3.interpolateRainbow;
  let count = 0;
  for (let f in all_graph_features){
    d[all_graph_features[f]] = d3.color(colorscheme(count++/all_graph_features.length)).darker(0.7)
  }
  return d;
}
```
  
<script>
// alphabetically sorted list to keep the color assignment consistent (remember this is resorted later for the interactive filtering)
// please then also adapt the styles.css, the code for which is generated in the ojs block below
graph_feature_tags = [
    "acyclic",
    "Bipartite",
    "bundled edges (generated)",
    "categorical nodes",
    "clusters",
    "clusters (generated)",
    "dense",
    "directed edges",
    "dynamic",
    "dynamic (discrete)",
    "edge weighted",
    "generic",
    "Hierarchical",
    "hypergraph",
    "known crossing number",
    "labeled nodes",
    "large",
    "N-layers",
    // "many layers",
    "mesh",
    "multigraph",
    "node weighted",
    "nonplanar",
    "partition",
    "planar",
    "signed",
    "sparse",
    "spatial",
    "temporal",
    "temporal event sequence",
    // "tree-like",
    "Trees"
]

graph_feature_tags_colors = [
    "#9B9A97", 
    "#64473A", 
    "#D9730D", 
    "#DFAB01", 
    "#0F7B6C", 
    "#0B6E99", 
    "#6940A5", 
    "#AD1A72", 
    "#E03E3E"
]

function name_cleanup(name){
  return name.replaceAll("(", "").replaceAll(")", "").replaceAll(" ", "_").replaceAll(".", "").replaceAll("'", "").replaceAll("&", "").replaceAll(" ", "").replaceAll(",", "")
}

// fallback function if adding a class is not an option
function get_css_color_for_tag(graph_feature_name) {
  return graph_feature_tags_colors[graph_feature_tags.indexOf(graph_feature_name)%graph_feature_tags_colors.length]
}

// The following provides output to be added to the styles.css manually, since quartro cannot hanlde dynamically injected css
    
// add new custom style because the compilation destroys the styles.css (not found under document.styleSheets)
//let targetStyle = document.createElement('style');
//document.head.appendChild(targetStyle);

//console.log(targetStyle.sheet)

let new_style = ""

// Dynamically add CSS rules for each tag
graph_feature_tags.forEach((graph_feature_name) => {
    const clean_css_tag_name = name_cleanup(graph_feature_name);
    const rule = `.pill_color_${clean_css_tag_name} { background-color: ${get_css_color_for_tag(graph_feature_name)}; }`;
    
    new_style += rule + "\n"
    
    /*try {
        targetStyle.sheet.insertRule(rule, targetStyle.sheet.cssRules.length);
    } catch (e) {
        console.error('Failed to insert rule:', e);
    }*/
});

// uncomment this to get the current color mapping for the tags to be added to the style.css
//console.log(new_style)

//console.log('Number of CSS rules added:', targetStyle.sheet.cssRules.length);
// Log each rule
//Array.from(targetStyle.sheet.cssRules).forEach(rule => {
//    console.log(rule.cssText);
//});

</script>

{{< include chapters/background.qmd >}}

{{< include chapters/collection_process.qmd >}}

{{< include chapters/additional_dataset_work.qmd >}}

{{< include chapters/datasets_in_use.qmd >}}

{{< include chapters/random_generation.qmd >}}

{{< include chapters/discussion.qmd >}}

## References {.unnumbered}

::: {#refs}
::: 
 


<script>
  document.querySelectorAll('a.dataset-link').forEach(item => {
        item.addEventListener('click', function (e) {
            // jumping is done by default with these links, we just need to get the collapsible to open up
            let str = this.getAttribute('href')
            // console.log('Link to ' + str + ' was clicked!'); // remember the str here has the hashtag in front!

            // Prepare the identifier
            // Remove the first character, assumed to hashtag 
            const ident = str.split('#')[1] || '';

            // find all the divs classed callout-titled and close them
            document.querySelectorAll('.callout-titled').forEach(item => {
                item.children[0].setAttribute('aria-expanded', 'false');
                item.children[1].classList.remove('show');
            });

            // find a div where the result of the function name_cleanup on its title attribute is equal to ident
            let foundDiv = [...document.querySelectorAll(".callout-titled")].find(d =>
                    typeof d.getAttribute('title') === 'string'
                    && (
                        name_cleanup(d.getAttribute('title')) == ident || d.getAttribute("data-collapse-id") == ident
                    )
            ); 

            if (foundDiv) {
                //console.log('Found div:', foundDiv);

                // Accessing the children of foundDiv
                const children = foundDiv.children;
                if (children.length >= 2) {
                    // Assume the first child is the header and the second is the content container
                    const header = children[0];
                    const content = children[1];

                    // Set aria-expanded to true on the header, this rotates the arrow icon on the right
                    header.setAttribute('aria-expanded', 'true');

                    // Add the 'show' class to the content container, this enables the content to be shown
                    content.classList.add('show');
                } else {
                    console.error('Expected at least two children in the div');
                }
            } else {
                console.error('Div not found');
            }
        });
    });
  </script> 