GLADOS: Graph Layout Algorithm benchmark Datasets for Open Science

(Zhu et al. 2021)

(Didimo, Liotta, and Montecchiani 2019)

(Demel et al. 2018)

(Devkota et al. 2019)

(Battista et al. 1997)

(Giacomo et al. 2020)

(Didimo, Liotta, and Patrignani 2018)

(Dwyer et al. 2013)

(Förster, Kaufmann, and Raftopoulou 2021)

(Ersoy et al. 2011)

(Firman et al. 2019)

(Forster 2002)

(Forster 2005)

(Y. Frishman and Tal 2008)

(Fruchterman and Reingold 1991)

(Fulek and Tóth 2018)

(Gange, Stuckey, and Marriott 2011)

(E. R. Gansner et al. 1993)

(Emden R. Gansner, Koren, and North 2005)

(E. R. Gansner, Koren, and North 2005)

(Emden R. Gansner and Koren 2006)

(E. R. Gansner, Hu, and North 2013)

(Gibson, Faith, and Vickers 2012)

(Giovannangeli et al. 2021)

(Gronemann 2016)

(Gronemann et al. 2016)

(Gutwenger and Mutzel 2004)

(Hachul and Jünger 2005)

(Kindermann, Meulemans, and Schulz 2018)

(Heinsohn and Kaufmann 2018)

(Henry, Fekete, and McGuffin 2007)

(D. Holten 2006)

(Danny Holten and Wijk 2009)

(Hong et al. 2019)

(Huang et al. 2016)

(Hummel et al. 2019)

(Jabrayilov et al. 2016)

(Jacomy et al. 2014)

(Jünger, Mutzel, and Spisla 2018)

(Y. Koren 2005)

(Klawitter, Mchedlidze, and Nöllenburg 2018)

(Klawitter and Zink 2021)

(Klemz et al. 2021)

(Lim and Kobourov 2021)

(Lin et al. 2010)

(M. Liu et al. 2017)

(Mallach 2019)

(Marner et al. 2014)

(Meidiana et al. 2019)

(Meulemans et al. 2013)

(Misue and Akasaka 2019)

(Nachmanson et al. 2017)

(Cao et al. 2011)

(Ni et al. 2018)

(Nickel et al. 2019)

(Niedermann and Rutter 2020)

(Nöllenburg 2010)

(Nöllenburg, Villedieu, and Wulms 2021)

(Nollenburg and Wolff 2011)

(Ogawa and Ma 2010)

(Oikonomou and Symvonis 2018)

(Olszewski et al. 2018)

(Ortali and Tollis 2018)

(Ortmann, Klimenta, and Brandes 2017)

(Perri and Scholtes 2020)

(Purchase et al. 2020)

(Qu, Zhang, and Zhang 2022)

(Raj and Whitaker 2018)

(Rüegg et al. 2016)

(Sander 1996)

(S. Liu et al. 2013)

(Simonetto, Archambault, and Kobourov 2018)

(Skambath and Tantau 2016)

(Sugiyama, Tagawa, and Toda 1981)

(Xue et al. 2023)

(H.-Y. Wu, Nollenburg, and Viola 2020)

(Walter et al. 2020)

(Cui et al. 2008)

(Wongsuphasawat et al. 2018)

(J. Wu et al. 2018)

(Zhang and Li 2010)

(A. Arleo, Miksch, and Archambault 2022)

(Barth, Jünger, and Mutzel 2002)

(Bast, Brosi, and Storandt 2020)

(Batik et al. 2022)

(M. A. Bekos et al. 2022)

(Binucci et al. 2022)

(Binucci, Didimo, and Patrignani 2023)

(Brandes and Wagner 1998)

(Brandes and Köpf 2002)

(Brandes and Pich 2006)

(Brandes and Pich 2009)

(M. Burch et al. 2011)

(M. Burch, Hlawatsch, and Weiskopf 2017)

(Chimani, Gutwenger, and Mutzel 2006)

(Chimani et al. 2010)

(Civril, Magdon-Ismail, and Bocek-Rivele 2006)

(Cohen 1997)

(Cornel et al. 2016)

(Cypko et al. 2017)

(Davidson and Harel 1996)

(Col, Klute, and Nöllenburg 2019)

(Devkota and Isaacs 2018)

(Di Bartolomeo, Pister, et al. 2022)

(Di Bartolomeo, Riedewald, et al. 2022)

(EADES 1984)

(De Luca, Hossain, and Kobourov 2019)

(Wang et al. 2019)

(Frick, Ludwig, and Mehldau 1995)

(Y. Frishman and Tal 2004)

(Yaniv Frishman and Tal 2007)

(Giovannangeli et al. 2023)

(Gove 2019)

(Gray et al. 2023)

(Greilich, Burch, and Diehl 2009)

(Hachul and Juenger 2005)

(Harel and Koren 2001)

(Hoffswell, Borning, and Heer 2018)

(Hofmann et al. 2017)

(Y. F. Hu 2005)

(Jünger and Mutzel 1996)

(Kamada and Kawai 1989)

(Yehuda Koren, Carmel, and Harel 2002)

(Kruiger et al. 2017)

(Lukasczyk et al. 2017)

(Meidiana et al. 2020)

(Meidiana, Hong, and Eades 2020)

(Meidiana, Hong, and Eades 2023)

(Mennens, Scheepens, and Westenberg 2019)

(Miller, Huroyan, and Kobourov 2023)

(Minghim, Paulovich, and Lopes 2006)

(Mizuno et al. 2019)

(Saket, Scheidegger, and Kobourov 2016)

(Muelder and Ma 2008b)

(Noack 2004)

(Nocaj, Ortmann, and Brandes 2015)

(Padia, Bandara, and Healey 2018)

(Padia, Bandara, and Healey 2019)

(Gajer and Kobourov 2000)

(Preiner et al. 2020)

(Dijk et al. 2016)

(Dijk et al. 2018)

(Elzen et al. 2013)

(Landesberger et al. 2016)

(Wallinger et al. 2023)

(Walshaw 2001)

(Wang et al. 2018)

(Wang et al. 2020)

(Welch and Kobourov 2017)

(Zarate et al. 2018)

(Zeng et al. 2019)

(Zheng, Pawar, and Goodman 2019)

(Zhong et al. 2023)

{
    //console.log(benchmark_datasets)
    
    // sorry for all the vars instead of let but this was split before into different cells
    var uniqueDataTagSet = new Set(); // set for the tags
    var uniquePaperTagSet = new Set();
    var dataSetNames = []; // list of names of datasets
    var paperNames = []
    var dataMap = {} // maps from the tags to the individual datasets
    var paperMap = {} // maps from the tags to the individual papers
    var nameMap = {} // maps from the cleaned name to the actual name containing potentially special characters

    //console.log(literature)
    // "Citation name": "bekos2022"
    // "Graph feature": "hypergraphs, spatial"
    
    const tagMapping = {
    "hypergraphs": "Hypergraphs",
    "spatial": "Spatial",
    "layered graphs": "N-layers",
    "generic": "Generic",
    "large": "Large",
    "dynamic (discrete)": "Dynamic",
    "dynamic": "Dynamic",
    "dynamic (continuous)": "Dynamic",
    "clusters (generated)": "Clusters (generated)",
    "clusters (pre-existing)": "Clusters (pre-existing)",
    "bundled edges (generated)": "Bundled edges (generated)",
    "directed edges": "Directed edges",
    "weighted edges": "Weighted edges",
    "weighted nodes": "Weighted nodes",
    "hierarchical": "Hierarchical",
    "categorical nodes": "Categorical nodes",
    "trees": "Trees",
    "labeled nodes": "Labeled nodes",
    "bipartite": "Bipartite",
    "tripartite": "Bipartite",
    "labeled edges": "Labeled edges",
    "planar": "Planar",
    "sparse": "Sparse",
    "K-planar": "Planar",
    "2-planar": "Planar",
    "acyclic": "Acyclic",
};

    
    benchmark_datasets.forEach((entry) => {
        let name = name_cleanup(entry.Name)
        nameMap[name] = entry.Name
        dataSetNames.push(name);
        var parts = entry["graph features handled"].split(",").map(item => item.trim())
        for (var part of parts) {
            if (part !== "") {
                uniqueDataTagSet.add(part);
                if (!dataMap[part]) {
                    dataMap[part] = new Set();
                }
                dataMap[part].add(name);
            }
        }
    })
     
    
     
  
    literature.forEach((paper) => {

      paperNames.push(paper["Citation name"]);
      var parts = paper["Graph feature"].split(",").map(item => item.trim())
      for (var part of parts) {
        if (part !== "") {
          uniquePaperTagSet.add(part);
          
          if (part in tagMapping) {
              part = tagMapping[part]
          }
          if (!paperMap[part]) {
              paperMap[part] = new Set();
          }
          
          paperMap[part].add(paper["Citation name"]);
        }
      }
    })
  
    // Add keys not present in the paperTags 
    Object.keys(dataMap).forEach((key) => {
      if (!paperMap[key]) {
        paperMap[key] = new Set();
      }
    })
  
  
    
    var category_tags = {
        0: "Layered",
        2: "Hierarchical",
        4: "Attributes",
        11: "Structures",
        21: "Other",
    }
    
    // if you change this ordering or move around values also change the category map above!!!
    //var uniqueDataTags = [...uniqueDataTagSet]
    var uniqueDataTags = [
        // Layered
        "Bipartite",
        "N-layers",
        
        // Hierarchical
        "Trees",
        "Hierarchical",

        // Attributes
        "Dynamic",
        "Weighted edges",
        "Weighted nodes",
        "Labeled nodes",
        "Categorical nodes",
        "Signed",
        "Spatial",
        
        // Structures
        "Clusters (pre-existing)",
        "Clusters (generated)",
        "Directed edges",
        "Hypergraphs",
        "Bundled edges (generated)",
        "Partition",
        "Multigraph",
        "Acyclic",
        "Mesh",

        // Other
        "Generic",
        "Planar",
        "Nonplanar",
        "Known crossing number",
        "Large",
        "Dense",
        "Sparse",
    ]
    var uniquePaperTags = [...uniquePaperTagSet]  
    //console.log(uniqueDataTags)
    //console.log(uniquePaperTagSet)
    //console.log(dataMap)
    //console.log(paperMap)
    //console.log(dataSetNames)
    //console.log(paperNames)

    // remove empty entries
    paperNames = paperNames.filter(str => str.trim() !== "")
    


    var checkBoxContainer = document.getElementById('checkbox-container');
    var linksListContainer = document.getElementById('datasetlinkslist-container')
    var paperLinksContainer = document.getElementById('paperlinkslist-container')
    var checkboxStates = [];  // Array to keep track of checkbox states (booleans)

    // needs to be in here since we access so many "global" variables
    function displayDataSetLinksList() {
        //console.log(checkboxStates); // current states to check which dataset links to display (index-based)

        const filteredTags = uniqueDataTags.map((item, index) => checkboxStates[index] ? item : undefined)
            .filter(item => item !== undefined);

        //console.log(filteredTags)

        var final_datasets = []
        var final_data_inverse = []

        var final_papers = []
        var final_paper_inverse = []

        if (filteredTags.length == 0) {
            final_datasets = dataSetNames;
            final_papers = paperNames;
        } else {
            // Retrieve an array of sets from the provided keys
            const dataSets = filteredTags.map(key => dataMap[key]);
            const paperSets = filteredTags.map(key => paperMap[key]);
            
            // Calculate the intersection of all sets
            const dataIntersection = dataSets.reduce((acc, set) => new Set([...acc].filter(x => set.has(x))));
            const paperIntersection = paperSets.reduce((acc, set) => new Set([...acc].filter(x => set.has(x))));
            
            final_datasets = [...dataIntersection] // white list
            final_papers = [...paperIntersection]

            // Now, compute the difference between dataSetNames and final_datasets
            const dataDifference = new Set(dataSetNames.filter(x => !final_datasets.includes(x)));
            const paperDifference = new Set(paperNames.filter(x => !final_papers.includes(x)));

            final_data_inverse = [...dataDifference]; // black list
            final_paper_inverse = [...paperDifference]
        }

        //console.log("show: " + final_datasets) // white list 
        //console.log("show: " + final_papers)

        final_datasets.forEach((name) => {
            //console.log(name + '-link')
            let currLinkDiv = document.getElementById(name + '-link')
            if (currLinkDiv != null) {
                currLinkDiv.style.display = 'block';  // Clear the display property to default ('block')
            } 
        })

        final_data_inverse.forEach((name) => {
            //console.log(name + '-link')
            let currLinkDiv = document.getElementById(name + '-link')
            if (currLinkDiv != null) {
                currLinkDiv.style.display = 'none';  // Hide the div
            }
        })

        final_papers.forEach((name) => {
            //console.log(name + '-link')
            let currLinkDiv = document.getElementById(name + '-link')
            if (currLinkDiv != null) {
                currLinkDiv.style.display = 'block';  // Clear the display property to default ('block')
            }
        })

        final_paper_inverse.forEach((name) => {
            //console.log(name + '-link')
            let currLinkDiv = document.getElementById(name + '-link')
            if (currLinkDiv != null) {
                currLinkDiv.style.display = 'none';  // Hide the div
            }
        })

      /*
      // this is how the it ran earlier and it was used to generate the static html links above this
      
      if (final_datasets.length == 0) {
      // display message that no dataset contains all these tags
      linksListContainer.innerHTML = '';
      } else {
      
      linksListContainer.innerHTML = '';
      
      final_datasets.forEach((currDataName) => {
      const anchor = document.createElement('a');
      anchor.href = '#' + currDataName
      anchor.classList.add('dataset-link')
      anchor.textContent = nameMap[currDataName]
      
      const div = document.createElement('div');
      div.id = currDataName + '-link'
      div.appendChild(anchor);
      
      linksListContainer.appendChild(div);
      })
      }
      
      // and here for the paper names
      paperNames = paperNames.filter(str => str.trim() !== "").sort();
      paperNames.forEach((currPaperName) => {

          const div = document.createElement('div');
          div.id = currPaperName + '-link'
          div.textContent = `[@${currPaperName}]`

          paperLinksContainer.appendChild(div);
      });*/
      
    }
   
  // Function to add a new checkbox with a styled span label
  function addCheckbox(index, name) {
      const newCheckbox = document.createElement('input');
      newCheckbox.type = 'checkbox';
      newCheckbox.id = 'checkbox' + index;
      newCheckbox.style.marginRight = '8px'; 
      newCheckbox.classList.add('form-check-input');

      // Creating the span that will act as a label
      const span = document.createElement('span');
      span.classList.add('pill-tag');
      span.classList.add(`pill_color_${name_cleanup(name)}`);
      //span.style.backgroundColor = get_css_color_for_tag(name)
      //span.style.backgroundColor = graph_feature_tags_colors[index % graph_feature_tags_colors.length];  
      span.textContent = name;

      const label = document.createElement('label');
      label.className = 'd-flex align-items-center justify-content-start';
      label.htmlFor = newCheckbox.id;
      label.style.cursor = 'pointer';  // Change the cursor to a pointer on hover
      label.appendChild(newCheckbox);
      label.appendChild(span);  // Append the span to the label

      const div = document.createElement('div');
      div.className = 'form-check d-flex align-items-center';  // Ensure the checkbox and label are aligned
      div.appendChild(label);

      checkBoxContainer.appendChild(div);

      // Update state array and add event listener
      checkboxStates.push(false);
      newCheckbox.addEventListener('change', () => {
          checkboxStates[index] = newCheckbox.checked;
          displayDataSetLinksList()
      });
  }

  // Automatically add checkboxes on load for each tag, we cannot reorder after this!
  uniqueDataTags.forEach((entry, index) => {
      if (category_tags.hasOwnProperty(index)) {
          const span = document.createElement('span');
          span.style.opacity = "50%";  // Setting it to be less obnoxious
          span.textContent = "\u2012 " + category_tags[index] + "\u2012 ";

          const div = document.createElement('div');
          div.className = 'd-flex align-items-center';  
          div.appendChild(span);

          checkBoxContainer.appendChild(div);
      }
      addCheckbox(index, entry);
  })

  // initial call to display all datasets (now a bit redundant but adds the "display" style-attribute)
  displayDataSetLinksList()

}

Uniform Benchmark datasets

Uniform Benchmark datasets are standalone widely used collections of graphs featuring uniform characteristics—usually simple, generic graphs, often used in evaluations that run over thousands of graphs to report average completion times, or other experiments where the reported metrics are usually aggregated.

Differently from the collections presented later in this section, an experiment that uses an Uniform Benchmark dataset aims to provide a general overview of the performance of a graph layout algorithm by testing on a large amount of graphs varying in size and density, rather than focusing on a specific type of graph.

The first of these collapsible sections is shown already expanded, to give an example of the content that can be found in each of them. The content is generated dynamically based on the data we collected.

Rome-Lib

Rome-Lib is, as previously discussed, the most common benchmark dataset, due to its already established popularity, its ease of use and access, and the many properties that are already known about it. It was first introduced in (Battista et al. 1997) and presented in their paper ”An experimental comparison of four graph drawing algorithms”. Mostly “real” networks such as software companies, government, software engineering books, database design, and journal articles on visualization. Originally sent as an extended abstract to Computational Geometry in 1995 (Di Battista, Garg, and Liotta 1995). It contains exclusively Genericgraphs (e.g., undirected, non-layered, without pre-established clusters…), although some of the research that uses it enhances with additional attributes (such as performing a rank assignment step). Information about optimal crossings can be found as part of WebCompute.

Originally found at: http://www.graphdrawing.org/data.html

Download formatted data: GEXF GML GRAPHML JSON

Size: 11534 graphs, 10 to 100 nodes, 9 to 158 edges

Origin paper:

(Battista et al. 1997)

An experimental comparison of four graph drawing algorithms

(Di Battista, Garg, and Liotta 1995)

An experimental comparison of three graph drawing algorithms (extended abstract)

Usage examples:

(Buchheim et al. 2008)

A branch-and-cut approach to the crossing number problem

(Chimani et al. 2010)

Layer-Free Upward Crossing Minimization

(Chimani, Gutwenger, and Mutzel 2006)

Experiments on Exact Crossing Minimization Using Column Generation

(Di Bartolomeo, Riedewald, et al. 2022)

Stratisfimal Layout: A modular optimization model for laying out layered node-link network visualizations

Clusters (pre-existing)Compound graphs Layered graphs N-layers

Aesthetic Discrimination of Graph Layouts

(Chimani, Mutzel, and Bomze 2008)

A New Approach to Exact Crossing Minimization

(Emden R. Gansner and Koren 2006)

Improved circular layouts

Circular

Deep Neural Network for Drawing Networks

(Gutwenger and Mutzel 2004)

An Experimental Study of Crossing Minimization Heuristics

(Battista et al. 1997)

An experimental comparison of four graph drawing algorithms

(Kindermann, Meulemans, and Schulz 2018)

A Note on the Practicality of Maximal Planar Subgraph Algorithms

Planar

Experimental Analysis of the Accessibility of Drawings with Few Segments

Sparse Trees

(Heinsohn and Kaufmann 2018)

An Interactive Tool to Explore and Improve the Ply Number of Drawings

(Demel et al. 2018)

A Greedy Heuristic for Crossing-Angle Maximization

(Michael A. Bekos et al. 2018)

A Heuristic Approach Towards Drawings of Graphs with High Crossing Resolution

(Niedermann and Rutter 2020)

An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings

Ortho Ortho-radial

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

An effective crossing minimisation heuristic based on star insertion

Advances in the Planarization Method: Effective Multiple Edge Insertions

An ILP-based Proof System for the Crossing Number Problem

Statistics

Descriptions from Literature

From “A branch-and-cut approach to the crossing number problem”:

To test the performance of our new algorithm, we used a benchmark set of graphs of the University of Rome III, introduced in [11]. The set contains 11 389 graphs that consist of 10 to 100 nodes and 9 to 158 edges. These graphs were generated from a core set of 112 “real life” graphs used in database design and software engineering applications. Most of the graphs are sparse, which is a common property in most application areas of automatic graph drawing. The average ratio between the number of edges and the number of nodes of the graphs from the benchmark set is about 1.35.

From “Layer-free upward crossing minimization”:

The Rome graphs [Di Battista et al. 1997] are a widely used benchmark set in graph drawing, obtained from a basic set of 112 real-world graphs. It contains 11,528 instances with 10 through 100 nodes and 9 through 158 edges. Although the graphs are originally undirected, they have been used as directed graphs—by artificially directing the edges according to the node order given in the input files—for showing the performance of the mixed-upward planarization approach [Eiglsperger et al. 2003]. In this case, all edges are directed and the graphs are acyclic; hence, the mixed-upward planarization approach turns into an upward planarization method.

From “A New Approach to Exact Crossing Minimization”:

We say graphs are trivial, if they are planar or if the heuristic achieves a planarization with only one crossing, as in these cases we need not prove optimality. The Rome library contains 7172 non-trivial graphs.

From “An Experimental Comparison of Four Graph Drawing Algorithms”

Our test graph generation strategy is as follows. First, we have focused on the important application area of database and software visualization, where Entity-Relationship diagrams and Data-Flow diagrams are usually displayed with orthogonal drawings. Second, we have collected 112 “real life” graphs with number of vertices between 10 and 100, from now on called core graphs, from the following sources:

• 54% of the graphs have been obtained from major Italian software companies (especially from Database Informatica) and large government organization (including the Italian Internal Revenue Service and the Italian National Advisory Council for Computer Applications in the Government (Autorita’ per l’Informatica nella Pubblica Amministrazione)); • 33% of the graphs were taken from well-known reference books in software engineering [18] and database design [1], and from journal articles on software visualization in the recent issues of Information Systems and the IEEE Transactions on Software Engineering; • 13% of the graphs were extracted from theses in software and database visualization written by students at the University of Rome “La Sapienza”.

Our approach is based on the following scheme. We defined several primitive operations for updating graphs, which correspond to the typical operations performed by designers of Entity-Relationship and Data-Flow Diagrams, and attributed a certain probability to each of them. More specifically, the updating primitives we have used are the following: InsertEdge, which inserts a new edge between two existing vertices; DeleteEdge, which deletes an existing edge; InsertVertex, which splits an existing edge into two edges by inserting a new vertex; DeleteVertex, which deletes a vertex and all its incident edges; and MakeVertex, which creates a new vertex and connects it to a subset of vertices. The test graphs were then generated in several iterations starting from the core graphs by applying random sequences of operations with a “genetic” mechanism. Namely, at each iteration a new set of test graphs was obtained by applying a random sequence of operations to the current test set. Each new graph was then evaluated for “suitability”, and those found not suitable were discarded. The probability of each primitive operation was varied at the end of each iteration. The evaluation of the suitability of the generated graphs was conducted using both objective and subjective analyses. The objective analysis consisted of determining whether the new graph had similar structural properties with respect to the core graph it was derived from. We have taken into account parameters like the average ratio between number of vertices and number of edges and the average number of biconnected components. The subjective analysis consisted in a visual inspection of the new graph and an assessment by expert users of Entity-Relationship and Data-Flow diagrams of its similarity to a “real-life” diagram. For obvious reasons, the subjective analysis has been done on a randomly selected subset of the graphs.

Example Figures

From ”An Experimental Comparison of Four Graph Drawing Algorithms”:

From “Experimental Analysis of the Accessibility of Drawings with Few Segments”:

From: Deep Neural Network for DrawiNg Networks, (DNN)2:

Fig 5. Layout examples for (DNN)^2, (DNN)^2, tsNET∗ and S_GD^2.

The following collections, together with Rome-Lib, can be easily accessed from the homepage of the Graph Drawing Conference website, and are therefore well known and widely used.

AT&T

Originally collected by Stephen North at AT&T Bell Labs (see the descriptions from literature section below for more information). The original link from 1995 is broken: ftp://ftp.research.att.com/dist/drawdag. Di Battista et al. modified the dataset by removing isomorphic graphs, connecting disconnected graphs, and removing cycles. Same as North DAG collection. It contains Directed edgesand Acyclic graphs.

Originally found at: http://www.graphdrawing.org/data.html

Download formatted data: GEXF GML GRAPHML JSON

Size: 1277 graphs, 10 to 100 nodes, 9 to 241 edges

Origin paper:

(Battista et al. 2000) Drawing Directed Acyclic Graphs: An Experimental Study

Usage examples:

(Hachul and Jünger 2005)

Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm

An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs

Large-Graph Layout with the Fast Multipole Multilevel Method

(Jabrayilov et al. 2016)

Compact Layered Drawings of General Directed Graphs

(Jünger, Mutzel, and Spisla 2018)

A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width

DAG Hierarchical Layered graphs N-layers

(Mallach 2019)

A Natural Quadratic Approach to the Generalized Graph Layering Problem

Layered graphs N-layers

Advances in the Planarization Method: Effective Multiple Edge Insertions

(Barth, Jünger, and Mutzel 2002)

Simple and Efficient Bilayer Cross Counting

Bipartite Layered graphs

Drawing Directed Acyclic Graphs: An Experimental Study

(Welch and Kobourov 2017)

Measuring Symmetry in Drawings of Graphs

Statistics

Descriptions from Literature

From “Drawing Directed Acyclic Graphs: An Experimental Study”:

The experimental study was performed on two different sets of DAGs, both with a strong connection to “real-life” applications. We considered two typical contexts where DAGs play a fundamental role, namely software engineering and project planning.

The first set of test DAGs are what we call the North DAGs. They are obtained from a collection of directed graphs [28], that North collected at AT&T Bell Labs by running for two years Draw DAG, an e-mail graph drawing service that accepts directed graphs formatted as e-mail messages and returns messages with the corresponding drawings [27].

Originally, the North DAGs consisted of 5114 directed graphs, whose number of vertices varied in the range 1 … 7602. However, the density of the directed graphs with a number of vertices that did not fall in the range 10 … 100 was very low (see also the statistics in [28]); since such directed graphs represent a very sparse statistical population we decided to discard them. Then we noted that many directed graphs were isomorphic; since the vertices of the directed graphs have labels associated with them, the problem is tractable. For each isomorphism class, we kept only one representative directed graph. Also, we deleted the directed graphs where subgraphs were specified as clusters, to be drawn in their own distinct rectangular region of the layout, because constrained algorithms are beyond the scope of this study. This filtering left us with 1277 directed graphs.

Still, 491 directed graphs were not connected and this was a problem for running algorithms implemented in G D W (they assume input directed graphs to be connected). Instead of discarding the directed graphs, we followed a more practical approach, by randomly adding a minimum set of directed edges that makes each directed graph connected. Finally, we made the directed graph acyclic, where necessary, by applying some heuristics for inverting the direction of a small subset of edges.

We then ran a first set of experiments and produced the statistics by grouping the DAGs by number of vertices. Although the comparison among the algorithms looked consistent (the produced plots never oddly overlapped), each single plot was not satisfactory, because it showed peaks and valleys. We went back to study the test suite and observed that grouping them by number of vertices was not the best approach. In fact, the North DAGs come from very heterogeneous sources, mainly representing different phases of various software engineering projects; as a result, directed graphs with more or less the same number of vertices may be either very dense or very sparse.

Since most of the analyzed quality measures strongly depend on the number of edges of the DAG (e.g. area, number of bends, and number of crossings), we decided that a better approach was to group the DAGs by number of edges. After some tests, we clustered the DAGs into nine groups, each with at least 40 DAGs, so that the number of edges in the DAGs belonging to group i, 1 ≤ i ≤ 9, is in the range 10 i … 10 i+9 (see Fig. 3). The resulting test suite consists of 1158 DAGs, each with edges in the range 10 … 99.

From “Layer-Free Upward Crossing Minimization”:

North DAGs. The North DAGs have been introduced in an experimental comparison of algorithms for drawing DAGs [Di Battista et al. 2000]. The benchmark set contains 1,158 DAGs collected by Stephen North, which were slightly modified by Di Battista et al. The graphs are grouped into nine sets, where set i contains graphs with 10 i to 10 i+9 arcs for i=1, …, 9.

Example Figures

From “Drawing Directed Acyclic Graphs: An Experimental Study”:

From “A Natural Quadratic Approach to the Generalized Graph Layering Problem”:

From “A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width”:

North DAGs

This is the same collection as AT&T, but referred to as North DAGs in the papers we analyzed. We kept the two collections separate, based on how they are referred to in the papers we collected.

Originally found at: See AT&T

Download formatted data: GEXF GML GRAPHML JSON

Size: See AT&T

Origin paper:

Drawing Directed Acyclic Graphs: An Experimental Study

Usage examples:

(Chimani et al. 2010)

Layer-Free Upward Crossing Minimization

A Note on the Practicality of Maximal Planar Subgraph Algorithms

Planar

(Rüegg et al. 2016)

A Generalization of the Directed Graph Layering Problem

(Demel et al. 2018)

A Greedy Heuristic for Crossing-Angle Maximization

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

An ILP-based Proof System for the Crossing Number Problem

Drawing Directed Acyclic Graphs: An Experimental Study

(Binucci et al. 2016)

Placing Arrows in Directed Graph Drawings

Directed edges

Aesthetic Discrimination of Graph Layouts

(Bachmaier, Gleißner, and Hofmeier 2012)

(Binucci et al. 2022)

Placing Arrows in Directed Graph Layouts: Algorithms and Experiments

Directed edges

Descriptions from Literature

From “Layer-Free Upward Crossing Minimization”:

North DAGs. The North DAGs have been introduced in an experimental comparison of algorithms for drawing DAGs [Di Battista et al. 2000]. The benchmark set contains 1,158 DAGs collected by Stephen North, which were slightly modified by Di Battista et al. The graphs are grouped into nine sets, where set \(i\) contains graphs with \(10 i\) to \(10 i+9\) arcs for \(i=1, \ldots, 9\).

RandDAG or DAGMar

The randDAG collection concludes the collections that can be easily accessed from graphdrawing.org. http://graphdrawing.org highlights the DAGmar graph generator, and provides a benchmark set of randomly generated directed acyclic graphs. While not explicit, it is implied this benchmark comes from the DAGmar generator. The collection is uniformly sampled from set of level graphs with certain graph parameters, such as number of nodes and number of edges. These graphs have no particular features, thus they are classified as Generic

Originally found at: http://www.graphdrawing.org/data.html

Download formatted data: GEXF GML GRAPHML JSON

Size: 10-100 nodes, 15-167 edges

Number of Graphs: 909

Origin paper:

DAGmar: Library for DAGs

Usage examples:

Aesthetic Discrimination of Graph Layouts

Statistics

Descriptions from the Literature

From “Aesthetic Discrimination of Graph Layouts”:

We have assembled such a dataset using two types of sources. First, we used the collections of the well-known graph archives ROME, NORTH and RANDDAG which are published on graphdrawing.org as well as the NIST’s “Matrix Market” [2].

Example Figures

From “Aesthetic Discrimination of Graph Layouts (Appendix)”:

Fig. 5. (cropped)… All graphs are visualized using the \(FM^3\) algorithm.

A very common problem in graph drawing is approximating or computing the exact crossing number of a graph. The datasets listed below are particularly useful when researchers are particularly useful for this task, as they contain graphs with Known crossing numbers, so that other algorithms’ results can be tested against them.

KnownCR

KnownCR is a collection of graphs with Known crossing numbers, and it is used to test the performance of algorithms that approximate the crossing number of a graph. The dataset is used in papers that aim to approximate the crossing number of a graph, and it is used to compare the results of the approximation algorithms to the known crossing numbers of the graphs. A good resource for this is also the survey provided by (Clancy, Haythorpe, and Newcombe 2019a). The graphs themselves do not appear to exist online elsewhere, but the method by which they can be created is fully described in (Gutwenger 2010).

Download formatted data: GEXF GML GRAPHML JSON

Size: 9-250 nodes, 18-750 edges

Origin paper:

(Gutwenger 2010)

Application of SPQR-Trees in the Planarization Approach for Drawing Graphs

Usage examples:

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

An effective crossing minimisation heuristic based on star insertion

Advances in the Planarization Method: Effective Multiple Edge Insertions

Statistics

Description from Literature

From “An effective crossing minimisation heuristic based on star insertion”:

KnownCR graphs- these are a set of instances containing between 9 and 250 vertices, first collected by Gutwenger [22], which can be further partitioned into four families of graphs as follows: \(C_i \times C_j\): The Cartesian product of the cycle on \(i\) vertices with the cycle on \(j\) vertices. The instances contain graphs with \(3 \leq i \leq 7\) and \(j \geq i\) such that \(ij \leq 250\). \(G_i \times P_j\): The Cartesian product of the path on \(j+1\) vertices with one of the 21 non-isomorphic connected graphs on 5 vertices, where \(i\) denotes which of the 21. The instances contain graphs with \(3 \leq j \leq 49\). \(G_i \times C_j\): The Cartesian product of the cycle on \(j\) vertices with one of the 21 non-isomorphic connected graphs on 5 vertices, where \(i\) denotes which of the 21. The crossing number of these graphs is only known for some of the \(G_i\) and only these cases are included. The instances contain graphs with \(3 \leq j \leq 50\). The Generalised Petersen graphs \(P(j,2)\) and \(P(j,3)\), on \(2j\) vertices. We shall only use those of type \(P(j,3)\) as \(P(j,2)\) (studied in [20]) are easy for heuristics to solve, as has already been observed in [9]. The instances contain graphs with \(9 \leq j \leq 125\).

From “Advances in the Planarization Method: Effective Multiple Edge Insertions”:

Finally, the KnownCR graphs [11] are a collection of 1946 graphs with known crossing numbers (by proofs), consisting of generalized Petersen graphs (P(m, 2), P(m, 3)) and products of cycles \(C_n\), paths \(P_n\), and 5-vertex graphs \(G_i (C_m \times C_n, G_i \times P_n, G_i \times C_n)\); these graphs have between 9 and 250 nodes.

Example Figures

From “Application of SPQR-Trees in the Planarization Approach for Drawing Graphs”:

WebCompute

The dataset is comprised of instances of graphs uploaded to Crossing Number WebCompute, attributed to Chimani and Wiedera (2016b). Their website also features proofs of the crossing numbers of many of the Rome-Lib graphs. Newest version of database specifies non-planar graphs, but older versions do have some planar graphs.

Originally found at: https://tcs.uos.de/doku.php?id=research/cr

Download formatted data: GEXF GML GRAPHML JSON

Size: 3-112 nodes, 3-366 edges

Number of Graphs: 507

Origin paper:

An ILP-based Proof System for the Crossing Number Problem

Usage examples:

An ILP-based Proof System for the Crossing Number Problem

Statistics

Descriptions from Literature

From “An ILP-based Proof System for the Crossing Number Problem”:

To determine the applicability of the proof system, we tested the algorithms on three benchmark sets: the 3110 non-trivial Rome graphs [14], the 1277 North graphs [15], and the145 non-planar graphs (http://crossings.uos.de/instances) collected by our crossing number web-service.

Complete Graphs

Complete graphs refers to a generic collection of graphs that are fully connected, i.e., each node is connected to every other node, up to any number of nodes that are needed for the purpose of the experiment. The linked dataset includes both the complete graphs \(K_n\) for \(5≤n≤50\) and the complete bipartite graphs \(K_{n_1,n_2}\) for \(5≤n1,n2≤40\). Crossing number is conjectured for most of these, and while not proven, we found these used in papers to validate minimum crossing numbers. We also note that the papers in our literature review did not provide example figures.

Download formatted data: GEXF GML GRAPHML JSON

Size: 5-80 nodes, 10-1600 edges

Number of Graphs: 1342

Usage examples:

An effective crossing minimisation heuristic based on star insertion

Statistics

Descriptions from Literature

From “An effective crossing minimisation heuristic based on star insertion”:

Complete graphs - Although the crossing number of the complete graph \(K_n\) is not known for for \(n ≥ 13\), the value is conjectured, and typically assumed to be correct. We compare the nine combinations of schemes to see how close to the conjectured value each of them is able to get, for various sizes of complete graphs up to \(n = 50\). We indicate how many crossings are obtained after the initial embedding, as well as at the conclusion of the heuristic. We also provide the runtimes, again separated into time spent producing the initial embedding, and time spent in the main loop of the heuristic.

Complete bipartite graphs - Much like the complete graphs, the crossing number of the complete bipartite graph \(K_{n1,n2}\) is only known in general for \(n_1 ≤ 6\), but the value is conjectured and typically assumed to be correct. Again, we compare the nine combinations of schemes to see how close to the conjectured value they can get for values up to \(n_1,n_2 = 40\), and report the same data as for the Complete graphs.

The crossing number of the complete graph \(K_n\) is conjectured (e.g. see Guy [25]) to be equal to \(H(n) := 1/4 \left\lfloor n/2\right\rfloor \left\lfloor (n − 1)/2\right\rfloor \left\lfloor(n − 2)/2\right\rfloor \left\lfloor (n − 3)/2\right\rfloor\). Although this conjecture is widely believed to be correct, it has only been confirmed for \(n ≤ 12\) despite considerable effort to extend the results further [30]. We ran the graphs \(K_n\) for \(5 ≤ n ≤ 50\). Each graph was run with 100 random permutations and the minimum found solution was compared to \(H(n)\) by computing the percent relative deviation from \(H(n)\)… For these graphs, we observe that when \(n\) was odd, every scheme combination was able to obtain a drawing with \(H(n)\) crossings. However, when \(n\) was even, each scheme reached a value which was usually very close but not equal to \(H(n)\).

The crossing number of the complete bipartite graph \(K_{n_1,n_2}\) is conjectured (e.g. see Zarankiewicz [35]) to be equal to \(Z(n_1, n_2) := \left\lfloor n_1/2\right\rfloor \left\lfloor (n_1 − 1)/2\right\rfloor \left\lfloor n_2/2\right\rfloor \left\lfloor (n_2 − 1)/2\right\rfloor\). We ran the graphs \(K_{n_1,n_2}\) for \(5 ≤ n1 ≤ n2 ≤ 40\). Each graph was run with 100 random permutations and the minimum found solution was compared to \(Z(n_1,n_2)\)… As can be seen in Table 6, QuickCross was successful in obtaining the conjectured optimum in all cases and for all scheme combinations, except \(K_{30,30}\) and \(K_{40,40}\)

In some cases, authors of algorithms that deal with particular graph types might prefer to focus on collections with specific attributes, that might be attributes of the nodes, the edges or the entire graph. This is the case of Storylines (Movie_Plots) and Militarized Interstate_Disputes (MID) for Temporal event sequences and World Maps for Geographicaldata:

Storylines (Movie Plots)

The storylines dataset is particularly useful for Temporal event sequencevisualization because of its Dynamicaspect and Clusters (which also evolve through time). It is a collection of graphs that represent movie plots, and the nodes are the characters in the movie. The edges represent the interactions between the characters. This dataset was initially collected by Yuzuru Tanahashi, then stored on his homepage at UC Davis, which, unfortunately, got taken down after some time from its publication. This caused the dataset to be lost for a period of time, as none of the papers that used it provided a link to the dataset or stored it as part of their supplemental material. The experiments contained in such papers were then rendered non-reproducible because of the missing dataset. Through the help of personal connections at UC Davis, we were luckily able to recover the dataset.

Originally found at: UC Davis’ website, personal page which is now unavailable. Currently distributed here.

Download formatted data: GEXF GML GRAPHML JSON

Size: 698-24056 nodes, 357-23088 edges

Number of Graphs: 6

Origin paper:

Design Considerations for Optimizing Storyline Visualizations

Usage examples:

An Efficient Framework for Generating Storyline Visualizations from Streaming Data

Clusters (pre-existing)Dynamic Dynamic (discrete)Layered graphs N-layers

(S. Liu et al. 2013)

StoryFlow: Tracking the Evolution of Stories

Design Considerations for Optimizing Storyline Visualizations

(Gronemann et al. 2016)

Crossing Minimization in Storyline Visualization

Clusters (pre-existing)Dynamic (discrete)Layered graphs N-layers

(Dijk et al. 2018)

Computing Storyline Visualizations with Few Block Crossings

(Di Bartolomeo et al. 2021)

Sequence Braiding: Visual Overviews of Temporal Event Sequences and Attributes

(Di Bartolomeo, Riedewald, et al. 2022)

Stratisfimal Layout: A modular optimization model for laying out layered node-link network visualizations

Clusters (pre-existing)Compound graphs Layered graphs N-layers

Statistics

Descriptions from Literature

From “An efficient Framework for Generating Storyline Visualizations from Streaming Data”:

The datasets we used for this study were the three movie datasets (Star Wars, The Matrix, and Inception) [25] which have been used in previous research as benchmark datasets for measuring layout legibilities. Star Wars consists of 14 entities and 200 time steps. The Matrix consists of 14 entities and 100 time steps. Inception consists of 8 entities and 490 time steps.

From “Design Considerations for Optimizing Storyline Visualizations” (origin paper):

The basic form of the data applied in this visualization is simply a chronological list of interactions between various characters. These interactions between characters can be separated into a series of interaction sessions, each session representing the time span of a set of interacting characters. More precisely, we define an interaction session as a unit which holds three attributes: • initiation time, • duration, and • members. Initiation time corresponds to the time when the interaction session begins. Duration corresponds to the duration of the interaction session. Members corresponds to the set of characters involved in the interaction session. Each interaction session represents a time slot in the data where its members are interacting. Note that any change in the formation of members (e.g., a character leaving or joining) indicates a separate interaction session.

Example Figures

From “An Efficient Framework for Generating Storyline Visualizations from Streaming Data”:

From “StoryFlow: Tracking the Evolution of Stories”:

From “Crossing Minimization in Storyline Visualizations”:

Militarized Interstate Disputes (MID)

Collected as part of the Correlates Of War project, the dataset contains two disconnected Temporal event sequences

Originally found at: https://correlatesofwar.org/data-sets/MIDs/

Download formatted data: GEXF GML GRAPHML JSON

Size: The dataset consists of 2 disconnected temporal event sequence graphs, one with 11,766 nodes and 5,883 edges, and the other with 9,619 nodes and 8,017 edges.

Origin paper:

(Palmer et al. 2022)

The MID5 Dataset, 2011–2014: Procedures, coding rules, and description.

Usage examples:

Design Considerations for Optimizing Storyline Visualizations

Clusters (pre-existing)Dynamic Dynamic (discrete)Layered graphs N-layers

(S. Liu et al. 2013)

StoryFlow: Tracking the Evolution of Stories

Description From Literature

From Design Considerations for Optimizing Storyline Visualizations:

For the time-varying network, we use the Militarized Interstate Dispute (MID) network dataset [19].

For example, in the MID network dataset, which consists of 196 nations and 740 time steps, the genome length was reduced from 1714 to 432, allowing the algorithm to gain a considerable speedup.

From StoryFlow: Tracking the Evolution of Stories:

We conducted the experiment based on three movie datasets and a network dataset: Star Wars, Inception, The Matrix, and the MID network dataset (from 1817 to 1947).

Example Figures

From Design Considerations for Optimizing Storyline Visualization:

World Maps

Datasets contain various attributes for a few locations and their geographical adjacency, namely neighboring states, countries, and municipalities. World Bank country information transformed into a weight-vectors dataset. Some of the incomplete data was filled from disparate sources mentioned in the paper’s supplemental materials: https://doi.org/10.48550/arXiv.1908.07291. The collection contains 14 graphs with Dynamicand Spatialattributes, Categorical nodes and Weighted nodes

Originally found at: https://data.worldbank.org/indicator https://github.com/loizuf/StableDemersLP/tree/main/code/StableDemers_TVCG/data

Download formatted data: GEXF GML GRAPHML JSON

Size: 48-514 nodes, 205-2428 edges

Number of Graphs: 14

Origin paper:

(Nickel et al. 2019)

Computing Stable Demers Cartograms

Usage examples:

(Nickel et al. 2019)

Computing Stable Demers Cartograms

Dynamic Spatial

Statistics

Descriptions from Literature

From Computing Stable Demers Cartograms”:

We run experiments on real-world datasets. For time-series data, we expect a gradual change and strong correlation between the different values. For weight-vectors data, we expect more erratic changes and less correlation. We use two maps with rather different geographic structures: the first (World) is a map of world countries, having mixed region (country) sizes in a rather unstructured manner; the second (US) is a map of the 48 contiguous US states, having relatively high structure in sizes of its states, with large states in the middle and along the west coast and many smaller states along the east coast.

From Supplemental Materials, Appendix C of *“Computing Stable Demers Cartograms*”:

Example Figures

From Computing Stable Demers Cartograms”:

The collections presented here are particularly varied in features:

Graphviz Examples

While graphviz is a graph visualization software, its example gallery has proven useful to many researchers as a source of benchmark datasets. The graphs have various origins, most of which are described on the Graphviz https://www.graphviz.org/gallery/. Example graphs used to generate images with the https://www.graphviz.org for their https://www.graphviz.org/gallery/. These graphs are picked as graphviz examples because they are diverse in types of features they contain: together with generic graphs, there are also graphs with clusters layers Directed edgesand Labeled nodes

Originally found at: https://gitlab.com/graphviz/graphviz/-/tree/main/tests/graphs

Download formatted data: GEXF GML GRAPHML JSON

Size: 1-1464 nodes, 0-5806 edges

Origin paper:

(Emden R. Gansner and North 2000)

An open graph visualization system and its applications to software engineering

Usage examples:

(Gange, Stuckey, and Marriott 2011)

Optimal k-level planarization and crossing minimization

Layered graphs N-layers

(Nachmanson et al. 2017)

Node Overlap Removal by Growing a Tree

(Giovannangeli et al. 2023)

FORBID: Fast Overlap Removal by Stochastic GradIent Descent for Graph Drawing

Statistics

Descriptions from Literature

Our data includes the same set of graphs that was used by the authors of PRISM to compare it with other algorithms [6]. The dataset is available in the Graphviz open source package.

From “Optimal k-level planarization and crossing minimization”:

The first set of graphs are all the hierarchical network diagrams appearing in the GraphViz gallery [3]… Table 1 shows the results of minimizing edge crossings and maximizing planar subgraphs with MIP and SAT solvers, as well as the crossings resulting in the Graphviz heuristic layout for graphs from the GraphViz gallery.

Example Figures

From “FORBID: Fast Overlap Removal by Stochastic GradIent Descent for Graph Drawing”:

From “Optimal k-level planarization and crossing minimization”:

Scotch Graph Collection

Collection consisting of graphs from various sources including topological meshes, meshes related to physical problems (fluid dynamics, structural mechanics, combinatorial optimization), and interprocess communication graphs for a parallel computing implementation of a factorization solver. The SCOTCH software package is produced by the SCOTCH project whose goal is to study static mapping by the means of graph theory, using “divide and conquer’’ graph bipartitioning heuristics. The original link to the data (http://www.labri.u-bordeaux.fr/Equipe/PARADIS/Member/pelegrin/graph) is broken.

Originally found at: https://wotug.org/parallel/libraries/communication/scotch/Graphs/

Download formatted data: GEXF GML GRAPHML JSON

Size: The graphs range from 7 to 144649 nodes, and 10 to 1074393 edges.

Origin Notes: The https://gitlab.inria.fr/scotch/scotch is produced by the https://www.labri.fr/perso/pelegrin/scotch/ whose goal is to study static mapping by the means of graph theory, using “divide and conquer’’ graph bipartitioning heuristics. The original link to the data http://www.labri.u-bordeaux.fr/Equipe/PARADIS/Member/pelegrin/graph is broken.

Origin paper:

(Pellegrini 2012)

Scotch and PT-Scotch Graph Partitioning Software: An Overview

(Chevalier and Pellegrini 2008)

PT-Scotch: A tool for efficient parallel graph ordering

Usage examples:

(Harel and Koren 2001)

A Fast Multi-Scale Method for Drawing Large Graphs

(Yehuda Koren, Carmel, and Harel 2002)

ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs

(H.-Y. Wu, Nollenburg, and Viola 2020)

Statistics

Descriptions from Literature

From “ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs”:

Figure 10c, the 4elt graph, is yet another example of a graph with inherent diversity of distance scales.

Example Figures

From “A Fast Multi-Scale Method for Drawing Large Graphs”:

From “ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs”:

Otherwise, one might decide to focus on a particular domain:

Biological Pathways (KEGG)

According to kegg.jp, “the KEGG PATHWAY database is a collection of manually drawn graphical diagrams, called KEGG pathway maps, for metabolic pathways, signaling pathways, pathways involved in various cellular processes and organismal systems, and perturbed pathways associated with human diseases”. The pathway data is separated by module, but the individual modules can be combined into a large graph as visualized at https://www.kegg.jp/kegg-bin/show_pathway?map01100

Originally found at: https://www.kegg.jp/kegg/pathway.html#global

Download formatted data: GEXF GML GRAPHML JSON

Size: 47-292 nodes, 41-327 edges

Number of Graphs: 13

Origin paper:

(Kanehisa Laboratories 2023)

KEGG: Kyoto Encyclopedia of Genes and Genomes

Usage examples:

Multi-Level Area Balancing of Clustered Graphs

Categorical nodes Clusters (pre-existing)Labeled nodes

Statistics

Descriptions from Literature

From “Multi-Level Area Balancing of Clustered Graphs”:

KEGG Overview Pathway. Fig. 6 is the result of reproducing the KEGG overview pathway map using our approach. The color coding of the category here is directly retrieved from the original KEGG database [43], as similarly incorporated in Metabopolis [64] (see figures in supplementary materials, available online). We also set the same threshold for specifying unimportant vertices as in Metabopolis, so that readers can refer to the paper for comparison (Fig. 6). The advantage of this technique allows us to arrange the vertexts in a balanced fashion by pushing vertexts away from each other. This initially gives users an idea of how big each category is, and explicitly shows which reaction is classified under which category. Users can also identify sub-components effectively since those components with identical topological structures are aligned as neighbors. This also helps users to comprehend which structures are associated with certain types of pathways, such as small chains, stars, etc.

Example Figures

From “Multi-Level Area Balancing of Clustered Graphs”:

Co-Phylogenetic Trees

Collected by the authors of “https://almob.biomedcentral.com/articles/10.1186/s13015-014-0031-3. Each element of the data set is two binary co-phylogentic trees. “Caryophyllaceae & Microbotryum” and “Stinkbugs & Bacteria” are missing but our dataset includes all other files from “https://doi.org/10.1007/978-3-319-73915-1_27”. An additional dataset from “https://almob.biomedcentral.com/articles/10.1186/s13015-014-0031-3”, called “Wolbachia”, is included. Naturally, the data contains Trees

Originally found at: https://gitlab.inria.fr/erable/eucalypt/-/blob/master/html/PaperDatasets.zip

Download formatted data: GEXF GML GRAPHML JSON

Size: 13-773 nodes, 12-772 edges

Number of Graphs: 30

Origin paper:

(Donati et al. 2015)

EUCALYPT: efficient tree reconciliation enumerator

Usage examples:

(Calamoneri et al. 2018)

Visualizing Co-phylogenetic Reconciliations

Binary trees Trees

Statistics

Descriptions from Literature

From “EUCALYPT: efficient tree reconciliation enumerator”:

To test EUCALYPT, we selected 12 datasets from the literature. As we are mostly interested in host-parasite systems, the first 10 datasets concern such relations: EC Encyrtidae & Coccidae [23], GL Gopher & Lice [24], SC Seabirds & Chewing Lice [25], RP Rodents & Pinworms [26], SCF Smut Fungi & Caryophillaceus plants [27], PLML Pelican Lice ML [28] (the trees are generated through a maximum likelihood approach), PLMP Pelican Lice MP [28] (the trees are generated through a maximum parsimony approach), RH Rodents & Hantaviruses [29], PP Primates & Pinworm [30], and FD Fishs and Dactylogyrus [31].

In addition, we used a dataset of our own which corresponds to arthropod hosts and a bacterium genus, Wolbachia, living inside the cells of their hosts [32,33]. The datasets were chosen to provide a variety in terms of size of the host and parasite trees: those from the literature are relatively small (from 7 to 100 leaves), while our own data provide an example of much bigger host and parasite trees, each having 387 leaves. Moreover, we were careful that the selected datasets cover, as much as possible, a range of situations in terms of coevolution and of the expected frequencies of each event

Example Figures

From “Visualizing Co-phylogenetic Reconciliations”:

And finally, a collection of graph problems:

SteinLib

SteinLib is a collection of Steiner tree problems in graphs and variants. Their website has additional information about each problem in the dataset, including whether or not it has been solved. We omit two sets, Relay and EFST, from our provided data due to size constraints.

Originally found at: https://steinlib.zib.de/steinlib.php

Download formatted data: GEXF GML GRAPHML JSON

Size: 6-38,418 nodes, 9-221,445 edges

Number of Graphs: 1207

Origin paper:

(Koch, Martin, and Voß 2001)

SteinLib: An Updated Library on Steiner Tree Problems in Graphs

Usage examples:

From A Note on the Practicality of Maximal Planar Subgraph Algorithms:

A Note on the Practicality of Maximal Planar Subgraph Algorithms

Planar

Statistics

Descriptions from Literature

We use the non-planar graphs of the established benchmark sets North [12] (423 instances), Rome [11] (8249), and SteinLib [16] (586), all of which include real-world instances. In our plots, we group instances according to |V| rounded to the nearest multiple of 10; for Rome we only consider graph with ≥ 25 vertices.

Example Figures

From SteinLib: An Updated Library on Steiner Tree Problems in Graphs:

Additional interesting graphs can be found in the Graph Drawing Contest website.

Established Network Repositories

A popular choice is to use datasets from Established Network Repositories. These are ample collections, often organized in dedicated websites which also offer a few stats about the contained graphs. These collections are particularly useful when trying to locate a graph with a specific structure or property.

Because their hosts are already dedicated to the maintaining and reporting of information on these collections, we do not include here any storage of the data (which would be redundant) or report statistics on them. Rather, our analysis here is focused on highlighting their properties, origins, and ways in which they have been used.

Matrix Market

Compiled by the Mathematical and Computational Sciences Division of the Information Technology Laboratory of the National Institute of Standards and Technology, the Matrix Market is a repository of test data for use in comparative studies of algorithms for numerical linear algebra, featuring nearly 500 sparse matrices from a variety of applications, as well as matrix generation tools and services. It has been used for experiments with Genericgraphs, Largegraphs, and graphs with Weighted edges Each matrix entry is accompanied by metadata that includes the matrix name and identifier, dimensions (number of rows and columns), number of non-zero elements, symmetry type (symmetric, skew-symmetric, or general) and data type (real, complex, integer, or pattern). The website also provides visualizations of the matrices, helping users understand their structure and distribution of non-zero elements. Downloads are also provided in a variety of formats, including their own Matrix Market Exchange (MME) format, Harwell-Boeing, and MATLAB.

Originally found at: https://math.nist.gov/MatrixMarket/index.html

Download formatted data:

Note: A repository of test data for use in comparative studies of algorithms for numerical linear algebra, featuring nearly 500 sparse matrices from a variety of applications, as well as matrix generation tools and services.

Origin Notes: Compiled by the https://math.nist.gov/mcsd/ of the http://www.itl.nist.gov/ of the http://www.nist.gov/

Origin paper:

Matrix Market: a web resource for test matrix collections

Usage examples:

[link] Aesthetic Discrimination of Graph Layouts

[link] Drawing graphs by eigenvectors: theory and practice

[link] Eigensolver methods for progressive multidimensional scaling of large data

[link] Graph Drawing by Stress Majorization

Generic Weighted edges

[link] Sublinear Time Force Computation for Big Complex Network Visualization

Descriptions from Literature

From “Graph Drawing by Stress Majorization”:

The first example is the 1138Bus graph (|V|=1138, |E|=1458) from the Matrix Market repository [1]. This graph models a network of high-voltage power distribution lines. Figure 4 shows two layouts of this graph.

Example Figures

From “Drawing graphs by eigenvectors: theory and practice” (top two layouts are a Matrix Market graph):

From “Graph Drawing by Stress Majorization”:

Network Repository

The Network Repository was proposed in 2015 by Rossi and Ahmed of Purdue University as a visually interactive real world graph tool and database. Graphs in this repository are tagged with their real-world source, have in-depth analysis, and even a preview visualization of each individual graph. Types of graphs include social networks, infrastructure networks, biological networks, and many others. The repository also offers sources for individual graphs. It contains many graphs from other benchmark sets described here.

Originally found at: https://networkrepository.com/

Origin paper:

(Rossi and Ahmed 2015)

The Network Data Repository with Interactive Graph Analytics and Visualization

Usage examples:

Drawing Big Graphs Using Spectral Sparsification

(Alessio Arleo et al. 2019)

A Distributed Multilevel Force-Directed Algorithm

Clusters (generated)Generic

Descriptions from Literature

From “A Distributed Multilevel Force-Directed Algorithm”:

To evaluate the running time of MULTI-GILA, we used the REALGRAPHS and BIGGRAPHS benchmarks, which contain larger graphs extracted from both real-world applications and synthetic generators; see Table 4. The REALGRAPHS set includes the 5 largest real-world graphs (mainly scale-free graphs) used in the experimental study of GILA [5]. These graphs are taken from the Stanford Large Networks Dataset Collection [3] and from the Network Data Repository [46], and their number of edges is between 121523 and 1541514.

From “Drawing Big Graphs Using Spectral Sparsification”:

We used three data sets. The first set of graphs is taken from “defacto-benchmark” graphs, including the Hachul library, Walshaw’s Graph Partitioning Archive, the sparse matrices collection [6] and the network repository [24]. These include two types of graphs that have been extensively studied in graph drawing research: grid-like graphs and scale-free graphs.

Pajek

The Pajek Program for Large Network Analysis is a tool developed and hosted by Andrej Vlado and some of their colleagues. As part of this program, they later compiled relevant graphs and links to other datasets, which we call today the Pajek collection. As a curiosity, pajek means spider in Slovenian. Many of Pajek graphs have been included as part of the SuiteSparse Matrix Collection.

Originally found at: http://vlado.fmf.uni-lj.si/pub/networks/data/

Origin paper:

(Batagelj and Mrvar 2006)

Pajek datasets

Usage examples:

(Noack 2004)

Energy Models for Graph Clustering

(Meidiana et al. 2019)

A Quality Metric for Visualization of Clusters in Graphs

Descriptions from Literature

Airline Routing (Figure 5): The nodes of this graph represent US airports, and the (unweighted) edges represent direct flights. The probability that two airports are connected by a direct flight is strongly related to their geographical distance: Most direct flights are relatively short, and only few large hub airports are connected by direct long-range flights. The distances in the edge-repulsion LinLog layout resemble the relative geographical distances of the airports remarkably closely, given that the graph does not contain any explicit information about geographical distances.

Dictionary (Figure 7): The nodes represent terms in the Online Dictionary of Library and Information Science (ODLIS), and the edges represent hyperlinks. A hyperlink between two terms exists if one term is used to describe the meaning of the other term, and thus connects semantically related terms. The edge-repulsion LinLog layout indeed groups semantically related terms, which is better reflected in the VRML file on the supplementary web page than in Figure 7(c). Such a grouping is useful, for example, for discovering the global topic areas (like publishing, printing, information technology, etc.), for identifying entry points for the exploration of topics, or for finding semantically related terms even if they are not explicitly linked.

From “A Quality Metric for Visualization of Clusters in Graphs”:

We re-used some datasets from the validation experiments and created some new ones, listed in Table 2. We also selected real world graph datasets with existing vertex categorization, which are listed under the double line in Table 2. The datasets were taken from Pajek [2] and Stanford Network Analysis Project’s (SNAP) repository [23, 40].

Example Figures

SNAP (Stanford Network Analysis Platform)

The SNAP repository is a collection of datasets assembled as part of the Stanford Network Analysis Platform, which started in 2004 and launched their website in 2009. Well-known, widely used graph repository. A number of graphs that became relevant individually are included in SNAP, such as Enron, Amazon, Protein Interactions datasets and various Social Network graphs. SNAP contains Genericgraphs, directedand Undirectedgraphs, Dynamicgraphs and more. Graphs are presented with name and descriptions and a few statistics such as a general description, numbers of nodes and edges, source and reference information.

Originally found at: http://snap.stanford.edu/data/index.html

Size: 1008 unique graphs (excluding graph classification tasks consisting of 352,536 graphs)

Origin paper:

(Leskovec and Krevl 2014)

SNAP Datasets: Stanford Large Network Dataset Collection

Usage examples:

(Alessio Arleo et al. 2019)

A Distributed Multilevel Force-Directed Algorithm

(Meidiana et al. 2019)

A Quality Metric for Visualization of Clusters in Graphs

ForceAtlas2

a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software

A Random Sampling O

(Zhong et al. 2023)

Force-Directed Graph Layouts Revisited: A New Force Based on the T-Distribution

From “ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software”:

(Meidiana, Hong, and Eades 2023)

Shape-Faithful Graph Drawings

Mesh

Descriptions from Literature

We benchmarked our algorithm with a dataset of 68 networks from 5 to 23,133 nodes. We tried to gather varied networks corresponding to the actual use of Gephi (a lot of social networks, and scale-free networks in general). Most of these networks are from the Stanford Large Network Dataset Collection (http://snap. stanford.edu/data/) and include social networks (Facebook and Twitter ego-networks), collaboration networks (from Arxiv) and autonomous systems (peering information inferred from Oregon route-views).

Example Figures

From “ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software”:

Stanford GraphBase

Compiled by Donald Knuth, the Stanford Graphbase consists of programs and datasets for network analysis. The datasets accompany a textbook, “The Stanford GraphBase: A Platform for Combinatorial Computing”.

Originally found at: https://www-cs-faculty.stanford.edu/~knuth/sgb.html

Origin paper:

(Knuth 2009)

The Stanford GraphBase: A Platform for Combinatorial Computing

Usage examples:

(Kruiger et al. 2017)

Graph Layouts by t-SNE

Clusters (generated)Generic Planar Spatial

(Raj and Whitaker 2018)

Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs

Clusters (generated)Weighted edges

(Gronemann et al. 2016)

Crossing Minimization in Storyline Visualization

(Jünger and Mutzel 1996)

2-Layer Straightline Crossing Minimization

Bipartite Layered graphs

(Barth, Jünger, and Mutzel 2002)

Simple and Efficient Bilayer Cross Counting

Bipartite Layered graphs

A Random Sampling O

Descriptions from Literature

From “Crossing Minimization in Storyline Visualizations”:

Since the instances “Anna Karenina” and “Les Miserables” are very big, we have split them into chapters and sequences of chapters. The resulting test-bed is made of eight chapters, seven pairs of chapters, six triples of chapters and five quadruples of chapters from “Anna Karenina”, and five chapters, four pairs of chapters and three triples of chapters from “Les Mis ́erables”, plus the entire “Adventures of Huckleberry Finn”, “Inception-sf”, “Inception”, “Star Wars”, “The Matrix-sf”, and “The Matrix”.

From “Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs”:

The third dataset is a graph of character associations in the famous French novel Les Miserables (Fig. 5) [18]. This graph consists of 77 nodes, each representing a character in the novel, and 254 weighted edges where the weights represent the number of chapters that feature both characters associated with an edge. We see the that the main protagonist Valjean (marked in red) is placed prominently in all three visualizations (Fig. 5). However, other key characters in the plot such as Inspector Javert (blue) and Cosett (orange), who do not appear often with characters other than the protagonist (and thus have low betweenness centrality) are treated differently. While the radial layout relegates them to the periphery (far from Valjean) (Fig. 5b), MDS (Fig. 5a) paints a conflicting picture with regard to their centrality, e.g., Cosett’s node almost overlaps with Valjean despite its low centrality. In contrast, the proposed ARL (Fig.5c) is able to coherently convey the low centrality of the Inspector Javert and Cosett, as well as, their closeness to Valjean. The above issue of distance distortion appears to be a frequent occurrence in the radial layout due to many characters who have a low centrality value causing them to end up being packed in the outer periphery. A case of contrast is that of the character Bishop Myriel (green) who despite being associated with several characters, is only seen with Valjean once.

Example Figures

From “Crossing Minimization in Storyline Visualizations”:

From “Graph Layouts by t-SNE”:

lesmis is the GraphBase Les Miserables graph

From “Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs”:

SuiteSparse Matrix Collection

The SuiteSparse Matrix Collection, formerly known as the University of Florida Sparse Matrix Collection, is a comprehensive repository of 2893 sparse matrices. All graphs in SuiteSparse belong to groups which will have more information about the graphs and the sub-collections they belong to. In our Descriptions from the Literature section we also highlight a few tables with the specific graphs used in a couple of papers. From “The university of Florida Sparse Matrix Collection”, Davis and Hu describe the origin of this network repository. Namely they cite the Harwell-Boeing collection as the starting point for SuiteSparse, then called the University of Florida (UF) Sparse matrix collection, back in 1991. Other groups, or collections, have then been added to SuitseSparse through the years, mainly focusing on real-world matrices and other relevant problems related to them.

Originally found at: https://sparse.tamu.edu/

Size: 2893

Origin paper:

(Davis and Hu 2011)

The University of Florida Sparse Matrix Collection

Usage examples:

(E. R. Gansner, Hu, and North 2013)

A Maxent-Stress Model for Graph Layout

(Ortmann, Klimenta, and Brandes 2017)

A Sparse Stress Model

Large Weighted edges

Drawing Big Graphs Using Spectral Sparsification

(Hong et al. 2019)

Multi-level Graph Drawing Using Infomap Clustering

Multilevel

(Börsig, Brandes, and Pasztor 2020)

Stochastic Gradient Descent Works Really Well for Stress Minimization

Clusters (generated)Generic Planar Spatial

(Kruiger et al. 2017)

Graph Layouts by t-SNE

(Zheng, Pawar, and Goodman 2019)

Graph Drawing by Stochastic Gradient Descent

(Zhu et al. 2021)

DRGraph: An Efficient Graph Layout Algorithm for Large-scale Graphs by Dimensionality Reduction

(Zhong et al. 2023)

Force-Directed Graph Layouts Revisited: A New Force Based on the T-Distribution

(Miller, Huroyan, and Kobourov 2023)

Spherical Graph Drawing by Multi-dimensional Scaling

Clusters (generated)Generic

(Meidiana, Hong, and Eades 2023)

Shape-Faithful Graph Drawings

Mesh

Descriptions From Literature

From “A Sparse Stress Model”:

We conducted our experiments on a series of different graphs, see Tab. 1, most of them taken from the sparse matrix collection [9]. We selected these graphs as they differ in their structure and size, and are large enough to compare the results of different techniques. Two of the graphs, LeHavre and commanche, have predefined edge lengths that were derived from the node coordinates. We did not modify the graphs in any way, except for those that were disconnected, in which case we only kept the largest component.

From “A Maxent-Stress Model for Graph Layout”:

With the exception of graph gd, which is an author collaboration graph of the International Symposium on Graph Drawing between 1994 and 2007, the graphs used are from the University of Florida Sparse Matrix Collection [9]. Our selection covers a range of graph sizes, and includes mesh-like and other nonmesh graphs, and graphs from Brandes and Pich’s experimental study of distance scaling [5].

Table 2. Test Graphs

From “DRGraph: An Efficient Graph Layout Algorithm for Large-scale Graphs by Dimensionality Reduction”:

We perform experiments on a broad range of datasets selected from the University of Florida Sparse Matrix Collection [10] and tsNET [34] (Table 1).

Table 1. Test Datasets

Example Figures

From “The university of Florida sparse matrix collection”:

Fig. 13. A sample of matrices from the Collection, for the purpose of illustrating the complexity and diversity of matrices arising in real applications

From “DRGraph: An Efficient Graph Layout Algorithm for Large-scale Graphs by Dimensionality Reduction”:

Fig. 8. Visualizations of selected graph datasets using FR, KK, S.M., FM3, SFDP, PMDS, tsNET and DRGraph.

One more of such collections is Konect. At the time of writing, though, the website for Konect has been down for a while. Both the data and the website are still accessible through web archive—thus we do not consider this a lost collection.

Subsets of other collections

Some of the datasets mentioned in the papers have, after a certain time, been integrated into other, larger collections. This is a phenomenon that can happen through the years, through the redistribution and through the merging of different sources: the Walshaw dataset, for instance, was and still is distributed and cited as its own standalone dataset, but its graphs can be now found as part of many other larger collections. In order to keep precise records about the data, we kept these instances separated, in order to link papers to the individual dataset they used if they explicitly mention using one of these smaller collections. We classified these datasets as Subsets.

Walshaw

C. Walshaw, collected for an archive of graph partitions which has been maintained since 2000. These are multilevel mesh partitions of heterogeneous networks from a variety of domains.

We do not provide the data ourselves. Walshaw requests to be emailed for the distribution of the data, and so we link to their site and to the graphs found in the SuiteSparse Matrix Collection.

It has Weighted nodesand Weighted edgesgraphs, and the partitions of the 34 graphs are given with various partition sizes and imbalance percentages.

Originally found at: https://chriswalshaw.co.uk/partition/ where C. Walshaw requests to be emailed for the dataset at mailto:c.walshaw@gre.ac.uk. the individual graphs can also be found on the SuiteSparse Matrix Collection under different groups.

Size: 34 graphs, 2395-448695 nodes, 6837-3314611 edges. Node-weighted, edge-weighted. Partitions of the 34 graphs are given with various partition sizes and imbalance percentages.

Origin paper:

(Soper, Walshaw, and Cross 2004)

A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning

(Walshaw and Cross 2000)

Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm

Usage examples:

(Walshaw 2001)

A Multilevel Algorithm for Force-Directed Graph Drawing

(Yaniv Frishman and Tal 2007)

Multi-Level Graph Layout on the GPU

(Yehuda Koren, Carmel, and Harel 2002)

ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs

(Y. Koren 2005)

Drawing graphs by eigenvectors: theory and practice

(Civril, Magdon-Ismail, and Bocek-Rivele 2006)

SDE: Graph Drawing Using Spectral Distance Embedding

Efficient and High Quality Force-Directed Graph Drawing

Large-Graph Layout with the Fast Multipole Multilevel Method

(Hachul and Jünger 2005)

Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm

Drawing Big Graphs Using Spectral Sparsification

An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs

(Brandes and Pich 2006)

Eigensolver methods for progressive multidimensional scaling of large data

(E. R. Gansner, Koren, and North 2005)

Topological fisheye views for visualizing large graphs

Generic High degree Large

(Y. Frishman and Tal 2008)

Online Dynamic Graph Drawing

Dynamic

(Hong et al. 2019)

Multi-level Graph Drawing Using Infomap Clustering

Multilevel

A Random Sampling O

(Meidiana et al. 2020)

Sublinear Time Force Computation for Big Complex Network Visualization

Descriptions from Literature

From “An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs”:

The rest of the test graphs are taken from real-world applications. In particular, we selected graphs from the AT&T graph library [1], from C. Walshaw’s graph collection [20], and a graph that describes a social network of 2113 people that we obtained from C. Lipp.

From “A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph-Partitioning”:

The test graphs have been chosen to be a representative sample of small to medium scale real-life problems (mostly mesh-based) and include both 2D and 3D examples of nodal graphs (where the mesh nodes are partitioned) and dual graphs (where the mesh elements are partitioned). In addition there is a 3D semi-structured graph, cti, which is unstructured in the x−y plane but extended regularly along the z-axis. Finally the test suite includes three non mesh-based graphs (add32, vibrobox, bcsstk32) which arise from various scientific computing applications2. None of the graphs have either vertex or edge weights; such graphs are not widely available since most applications do not accurately instrument costs and it is difficult to draw meaningful conclusions from the few examples that we have access to.

Example Figures

From “An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs”:

From “Multi-Level Graph Layout on the GPU”:

Fig. 11. 4elt. Red: our layout, black: Kamada-Kawai layout

Other

From Group DIMACS10 in the SuiteSparse Matrix Collection:

Chris Walshaw's graph partitioning archive contains 34 graphs that
    have been very popular as benchmarks for graph partitioning algorithms
    ( http://staffweb.cms.gre.ac.uk/~wc06/partition/ ).

    17 of them are already in the UF Collection.  Only the 17 new graphs
    not yet in the collection are added here in the DIMACS10 set.

DIMACS10 graph:                 new?   UF matrix:
    ---------------                 ----   -------------
    walshaw/144                      *     DIMACS10/144
    walshaw/3elt                           AG-Monien/3elt
    walshaw/4elt                           Pothen/barth5
    walshaw/598a                     *     DIMACS10/598a
    walshaw/add20                          Hamm/add20
    walshaw/add32                          Hamm/add32
    walshaw/auto                     *     DIMACS10/auto
    walshaw/bcsstk29                       HB/bcsstk29
    walshaw/bcsstk30                       HB/bcsstk30
    walshaw/bcsstk31                       HB/bcsstk31
    walshaw/bcsstk32                       HB/bcsstk32
    walshaw/bcsstk33                       HB/bcsstk33
    walshaw/brack2                         AG-Monien/brack2
    walshaw/crack                          AG-Monient/crack
    walshaw/cs4                      *     DIMACS10/cs4
    walshaw/cti                      *     DIMACS10/cti
    walshaw/data                     *     DIMACS10/data
    walshaw/fe_4elt2                 *     DIMACS10/fe_4elt2
    walshaw/fe_body                  *     DIMACS10/fe_body
    walshaw/fe_ocean                 *     DIMACS10/fe_ocean
    walshaw/fe_pwt                         Pothen/pwt
    walshaw/fe_rotor                 *     DIMACS10/fe_rotor
    walshaw/fe_sphere                *     DIMACS10/fe_sphere
    walshaw/fe_tooth                 *     DIMACS10/fe_tooth
    walshaw/finan512                       Mulvey/finan512
    walshaw/m14b                     *     DIMACS10/m14b
    walshaw/memplus                        Hamm/memplus
    walshaw/t60k                     *     DIMACS10/t60k
    walshaw/uk                       *     DIMACS10/uk
    walshaw/vibrobox                       Cote/vibrobox
    walshaw/wave                           AG-Monien/wave
    walshaw/whitaker3                      AG-Monien/whitaker3
    walshaw/wing                     *     DIMACS10/wing
    walshaw/wing_nodal               *     DIMACS10/wing_nodal

Amazon

Wallinger et al. randomly filter data from the original dataset collected by Leskovec et al. in The dynamics of viral marketing. Leskovec et al. collected 15 million recommendations made from June 2001, to May 2003 by looking at the “Customers who Bought This Item Also Bought” feature in the Amazon online shopping platform. This dataset is a subset of SNAP and can be found there. It has directededges and Largegraphs.

Originally found at: http://snap.stanford.edu/data/#amazon

Size: 1 graph, 192k vertices and 269k edges

Origin paper:

(Leskovec and Krevl 2014)

SNAP Datasets: Stanford Large Network Dataset Collection

(Leskovec, Adamic, and Huberman 2007)

The dynamics of viral marketing

Usage examples:

Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach

From Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach:

Description from Literature

Amazon Subset This dataset consists of products with edges indicating that they are commonly co-purchased. We randomly filtered edges from the original graph [33], [34]. It has |V|=192k vertices and |E|=269k edges.

Example Figures

From Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach:

Autonomous System Network

The 733-AS network is a subset of SNAP. We provide the link containing the original project, https://www.routeviews.org/routeviews/, and redirect to SNAP, https://snap.stanford.edu/data/as-733.html for the network data. In the dataset description they highlight how the graphs exhibit node and edge addition and deletion over time.

The data was originally part of the University of Oregon’s RouteViews project. It was then used by Jure Leskovec et al. and eventually stored in SNAP. It contains dynamicgraphs.

Originally found at: https://www.routeviews.org/routeviews/ https://snap.stanford.edu/data/as-733.html https://github.com/csuvis/MCGS/blob/master/dataset/AS-733_edge.csv

Origin paper:

(Leskovec, Kleinberg, and Faloutsos 2005)

Preserving Minority Structures in Graph Sampling

Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations

Number of Graphs: 733

Usage examples:

Preserving Minority Structures in Graph Sampling

Descriptions from Literature

From “Preserving Minority Structures in Graph Sampling”

The AS-733 graph data set [48] is an autonomous systems network on the Internet with 6,474 nodes and 13,895 edges. The original graph and samples obtained by RDN, SST, MCGS are shown in Figure 5.

From “Graphs over time: densification laws, shrinking diameters and possible explanations”

The graph of routers comprising the Internet can be organized into sub-graphs called Autonomous Systems (AS). Each AS exchanges traffic flows with some neighbors (peers). We can construct a communication network of who-talks-towhom from the BGP (Border Gateway Protocol) logs. We use the the Autonomous Systems (AS) dataset from [26]. The dataset contains 735 daily instances which span an interval of 785 days from November 8 1997 to January 2 2000.In contrast to citation networks, where nodes and edges only get added (not deleted) over time, the AS dataset also exhibits both the addition and deletion of the nodes and edges over time.

Example Figures

From “Preserving Minority Structures in Graph Sampling”

Fig. 5. Case analysis of the AS-733 graph data set (a) and three samples generated by RDN (b), SST(c), and MCGS (d) with a sampling rate of 30%.

Control Flow Graphs

14 graphs from the GraphViz test suite collected by Gansner and Hu to evaluate their PRISM algorithm in ”https://dx.doi.org/10.7155/jgaa.00198”. This is just a subset of GraphViz, so we link to that dataset instead.

Size: 14 graphs, from 36 to 1463 nodes

Usage examples:

(Nachmanson et al. 2017)

Node Overlap Removal by Growing a Tree

Descriptions from Literature

Our data includes the same set of graphs that was used by the authors of PRISM to compare it with other algorithms [6]. The set is available in the Graphviz open source package.

Example Figures

Single Graphs

A number of papers used individual, Single Graphs for their experiments instead of a collection. These graphs have become popular because of their properties as individual graphs - see, for example, the Enron dataset below, a huge individual graph that has a large variance in node degree distribution. Many of these graphs are also available in other repositories - their locations are noted wherever known.

Enron

Data made public by the Federal Energy Regulatory Commission when investigating Enron. It has had a few changes over time documented in the link provided as its source. The data is currently hosted by William W. Cohen from CMU on a webiste, and it is also hosted on SNAP. SNAP asks to cite the paper linked in Origin paper. Very high variance in node degrees. Data can be considered threaded and directed, although SNAP provides a version of the network that is explicitly undirected. This dataset proves useful for evaluating algorithms that work on very large graphs, due to its very large size.

Originally found at: https://www.cs.cmu.edu/~enron/

Size: The data consists of 150 Enron executives, who sent 500,000 messages between themselves.

Origin paper:

(Klimt and Yang 2004)

Introducing the Enron Corpus

Usage examples:

An Efficient Framework for Generating Storyline Visualizations from Streaming Data

(Elzen et al. 2013)

Reordering massive sequence views: Enabling temporal and structural analysis of dynamic networks

Clusters (generated)Generic Large

Descriptions from Literature

From “Reordering massive sequence views: Enabling temporal and structural analysis of dynamic networks”:

We cleaned the data set by removing duplicates, spam and only to contain internal communication between Enron employees annotated with employee function leaving us with 151 nodes (employees) and 21374 edges (emails). Visualization using a node-link diagram enables the identification of stronger connections (see Figure 9(a)). However, temporal patterns and the evolution of the network cannot be analysed. From the standard MSV (Figure 9(b)) it becomes somewhat clear that transaction density increases over time and we can distinguish between different phases. We cannot, however, see features and identify communities due to visual clutter

Example Figures

From “An Efficient Framework for Generating Storyline Visualizations from Streaming Data”:

From “Reordering massive sequence views: Enabling temporal and structural analysis of dynamic networks”:

California

Data contains links related to an online search of the word “California” as nodes - the edges are links between webpages. We found this dataset on the webpage of a 2002 computer science course at Cornell, instructed by Jon Kleinberg. The original name was Pages that match the word “California”. They mention how the data was queried from a search engine, and that many of the original links are broken. It is not clear whether Kleinberg collected the data, or compiled it for the course.

Originally found at: https://www.cs.cornell.edu/courses/cs685/2002fa/data/gr0.California

Download formatted data: GEXF GML GRAPHML JSON

Size: 4772 nodes, 8965 edges

Origin paper:

(Kleinberg 2002)

The Structure of Information Networks

Usage examples:

(Muelder and Ma 2008b)

A Treemap Based Method for Rapid Layout of Large Graphs

Rapid Graph Layout Using Space Filling Curves

Clusters (pre-existing)Layered graphs N-layers

Statistics

Descriptions from Literature

From “A Treemap Based Method for Rapid Layout of Large Graphs”:

This particular graph is a non-weighted graph of links between search results for the word “California” (also in Figures 6, 8, and 9, |V|=6107,|E|=15160).

From “Rapid Graph Layout Using Space Filling Curves”:

The “california” dataset (shown in Figures 5 and 8) consists of the links between the webpages found from a search for the word ‘California’ [4].

Example Figures

From “A Treemap Based Method for Rapid Layout of Large Graphs”:

Fig. 1. A graph laid out using our treemap based approach. This graph portrays the links between websites that came from a search on the word “California” [7]. Nodes are clustered into a hierarchy, and laid out by applying a treemap to this hierarchy. Levels of the hierarchy below a threshold are clustered together into larger nodes. It can very easily be seen that there are three primary groups of websites that link to each other, and a plethora of others that are not as tightly linked.

From “Rapid Graph Layout Using Space Filling Curves”:

Fig. 5 Separating clusters. By adjusting the spacing between nodes according to the clustering information, clusters can be separated.

World Greenhouse Gas Emissions

Data collected by the WRI. Linked data is from a different year than the data used by Optimal Sankey Diagrams Via Integer Programming, for which data could not be found. Contains Weighted edges Weighted nodes Categorical nodes and layers

Originally found at: https://www.wri.org/data/world-greenhouse-gas-emissions-2005 https://www.wri.org/search?keys=world%20greenhouse%20gas%20emissions&f%5B0%5D=content_type%3Adata https://github.com/lhc70000/sankey/tree/master

Download formatted data: GEXF GML GRAPHML JSON

Size: 40 nodes, 85 edges

Origin paper:

(Baumert, Herzog, and Pershing 2005)

Navigating the Numbers: Greenhouse Gas Data and International Climate Policy

Usage examples:

(Zarate et al. 2018)

Optimal Sankey Diagrams via Integer Programming

Statistics

Descriptions from Literature

We have tested our method on the “World Greenhouse Gas Emissions” data from the World Resources Institute [8]. After transforming the “long” edges of the graph into “short” edges and adding the corresponding dummy nodes, as described in Section 3, this example has 4 layers, 55 nodes and 100 edges. The node ordering in the layout of the Sankey diagram shown in Figure 1 has been computed using Sugiyama’s heuristic method [13].

Example Figures

From Optimal Sankey Diagrams via Integer Linear Programming:

127.0.0.1:5501:150:21

Chess Games

20,058 chess openings from games in a database of played online chess games. The authors of “Sequence Braiding: Visual Overviews of Temporal Event Sequences and Attributes” collected the dataset online from the data science platform kaggle. The dataset was collected by user Mitchell J. and collects data from the chess website Lichess.org. The data used in the literature focuses on the 200 most common openings. These are all sequences of 6 moves and are topologically equivalent. It is a layered graph with Categorical nodesand Layers and can be seen as a Temporal event sequence

Originally found at: https://www.kaggle.com/datasets/datasnaek/chess?resource=download
https://github.com/VisDunneRight/sequence_braiding/blob/master/data/chess.json

Download formatted data: GEXF GML GRAPHML JSON

Size: The data consists of 20058 sequences, which result in a disconnected graph of 118164 nodes, and 98106 edges.

Origin paper:

(Jolly 2017)

Chess Game Dataset (Lichess)

Usage examples:

(Di Bartolomeo et al. 2021)

Sequence Braiding: Visual Overviews of Temporal Event Sequences and Attributes

Clusters (generated)Generic

Descriptions from Literature

From “Sequence Braiding: Visual Overviews of Temporal Event Sequences and Attributes”:

200 Chess openings displayed with Sequence Braiding. Each line represents a sequence of moves of the white player, each group is a chess piece type. Most openings start with a pawn, and very little with the knight.

Example Figures

From “Sequence Braiding: Visual Overviews of Temporal Event Sequences and Attributes”:

Fig. 7. 200 Chess openings displayed with Sequence Braiding. Each line represents a sequence of moves of the white player, each group is a chess piece type. Most openings start with a pawn, and very little with the knight. After moving a pawn, it is common to move a knight or a pawn, it is a little less common to move a bishop, and only a little number of openings move the queen on the second move.

Tree of Life

Part of the http://tolweb.org/tree/to characterize information about biodiversity and their evolutionary genealogy. It is a tree treewith Categorical nodes

Originally found at: https://www.kaggle.com/datasets/konivat/tree-of-life?resource=download

Download formatted data: GEXF GML GRAPHML JSON

Size: 35,960 nodes, 35,959 edges

Origin paper:

(Letunic and Bork 2021)

Interactive Tree Of Life (iTOL) v5: an online tool for phylogenetic tree display and annotation

(Maddison, Schulz, and Maddison 2007)

The Tree of Life Web Project

Usage examples:

(Gray et al. 2023)

Visualizing Evolving Trees

Dynamic Dynamic (discrete)

Descriptions from Literature

From “Visualizing Evolving Trees”:

The Tree of Life: captures the evolutionary progression of life on Earth [37]. The underlying data is a tree structure with a natural time component. As a new species evolves, a new node in the tree is added. The edges give the parent-child relation of the nodes, where the parent is the original species, and the child is the new species. We use a subset of this graph with 500 nodes. The maximum node degree of this tree is 5, and the radius is 24

Example Figures

From “Visualizing Evolving Trees”:

Fig. 4. Layouts obtained by the seven methods for the tree of life dataset.

World Bank Trade Data

Bilateral trade value in 1999 (total imports+exports), from wits.worldbank.org. It is denseand has Categorical nodes

Originally found at: https://wits.worldbank.org/module/ALL/sub-module/ALL/reporter/ALL/year/ALL/tradeflow/ALL/pagesize/50/page/1

Download formatted data: GEXF GML GRAPHML JSON

Size: 194 nodes, 10080 edges

Origin paper:

(Subramanian and Wei 2007)

The WTO promotes trade strongly but unevenly

Usage examples:

(Noack 2004)

Energy Models for Graph Clustering

(Nocaj, Ortmann, and Brandes 2015)

Untangling the Hairballs of Multi-Centered Small-World Online Social Media Networks

Statistics

Descriptions from Literature

The difference between conventional energy models, node-repulsion LinLog, and edge-repulsion LinLog can be illustrated with a model of the trade between ten North American and European countries. The nodes of the graph correspond to the countries, and the edge weights specify the trade volume between each pair of countries. Because of geographical closeness and free trade agreements, countries on the same continent trade more intensively than countries on different continents. Figure 1 shows the minimum energy layouts of the trade graph for the three force and energy models. The layout of the widely used Fruchterman-Reingold model [20] does not show any clear groups at all. The layout of the node-repulsion LinLog energy model groups the countries (nodes) primarily according to their total trade volume (degree). Only the layout of the edge-repulsion LinLog energy model shows the expected grouping according to continents.

Example Figures

From “Untangling the Hairballs of Multi-Centered Small-World Online Social Media Networks”:

From Methods for Visual Understanding of Hierarchical System Structures:

Investment Interdependence

Data collected in a survey of Ohio State University students by D. W. Malone. Students were presented with two potential obstacles to investment in Columbus, Ohio’s business district and asked, “does obstacle A aggravate or intensify obstacle B?”. Contains Directed edgesand is Hierarchical

Download formatted data: GEXF GML GRAPHML JSON

Size: 25 nodes, 30 edges

Origin paper:

(Malone 1975)

An introduction to the application of interpretive structural modeling

Usage examples:

(Sugiyama, Tagawa, and Toda 1981)

Methods for Visual Understanding of Hierarchical System Structures

Hierarchical Layered graphs N-layers

Statistics

Description from Literature

Presented in Fig. 5 are drawings of the nine-level hierarchy which appeared in Malone [11] and represent the interdependence of obstacles to investment in the Columbus, Ohio, central business district.

Example Figures

From Methods for Visual Understanding of Hierarchical System Structures:

Fig. 5. (cropped): Maps of the nine-level hierarchy [11]. (a) Initial. (b) BC + QP methods (c = 1.0). (c) BC + QP methods (cL= 0.5). (d) BC + QP methods (c = 0.05). (e) BC + PR methods.

Protein Interactions

Protein Interaction Publications were collected from the Biological Pathway Commons Database. Various types of protein interaction graphs are recorded in other network collections. We highlight two of them from the surveyed papers. First, we have the temporal Protein Interaction Publications, showing the history of how protein interactions were described in the literature. Second, the Protein Homology graph was provided by the Large Graph Layout project, their links are now broken and the dataset lost. Nonetheless, SNAP and Konect both also have various dataset of human/other species protein interactions.

Originally found at: https://github.com/CreativeCodingLab/TimeArcs/tree/master/IndexCards https://lgl.sourceforge.net/ (download link broken)

Download formatted data: GEXF GML GRAPHML JSON

Size: 2961 nodes, 5267 edges

Origin paper:

(Adai et al. 2004)

LGL: Creating a Map of Protein Function with an Algorithm for Visualizing Very Large Biological Networks

Usage examples:

Rapid Graph Layout Using Space Filling Curves

TimeArcs: Visualizing Fluctuations in Dynamic Networks

From TimeArcs: Visualizing Fluctuations in Dynamic Networks:

Protein Interaction Publications

Statistics

Description from the Literature

The data contains the publication information (such as publication year, author, and textual evidence) of interactions between pairs of proteins, as well as their specific interaction type.

When there are multiple arcs connecting two proteins, it falls into one of the two circumstances. If they have the same color, these arcs indicate that there are supporting evidences in different publications which confirm the interaction between two elements. On the other hand, if they have the different colors, the more recent appearance provides either more detailed knowledge about the interaction or shows a conflict between different articles regarding the way in which these proteins interact.

Example Figures

From TimeArcs: Visualizing Fluctuations in Dynamic Networks:

Fig. 10: TimeArcs visualization for interactions around PCAF protein. (1), (2), and (3) in the figure are supporting evidences in literature of “PCAF binds MAML”.

Protein Homology (Lost)

Description from the Literature

From [Rapid Graph Layout Using Space Filling Curves:](https://ieeexplore.ieee.org/document/4658143)

The “pgraph” dataset (shown in Figures 2 and 6) is a protein homology graph, which is relatively dense [7].

Consists of 28, 854 vertices and 1,180, 816 edges, found in Table 1 of paper above.

Example Figures

From Rapid Graph Layout Using Space Filling Curves:

Fig. 2. A protein homology graph laid out with our space filling curve based approach. Color corresponds to depth in the clustering hierarchy. |V| = 28, 854,|E| = 1, 180, 816

From LGL: Creating a Map of Protein Function with an Algorithm for Visualizing Very Large Biological Networks

Fig. 3. The complete protein homology map. A layout of the entire protein homology map; a total of 11,516 connected sets containing 111,604 proteins (vertices) with 1,912,684 edges. The largest connected set is shown more clearly in the inset and is enlarged further in Figure 4.

Aggregate Collections

Many papers use graphs from specific domains that contain particular characteristics, such as geographical coordinates often found in airline data. Instead of collecting each of these individual, contextual datasets, we aggregated them into subcategories called Aggregate collections. These collections group together datasets from the same real-life context, which may have multiple sources. Real-life contexts are distinguishable by specific properties or requirements found in graphs from those sources; for instance, collaboration networks can be represented as hypergraphs, while air traffic routes have nodes (airports) with fixed spatial coordinates and numerous edges connecting the nodes, making them suitable for edge bundling algorithms. Individual information about each aggregate collection can be found in the papers that contain them.

Assorted Collaboration Network

Contains IEEEVis Publication Data, DBLP collaborations, and CPAN, which contains collaboration information among developers using Perl. The VIS publication data was found online in the following website: https://sites.google.com/site/vispubdata. However, we also downloaded the text file fromhttps://www.cc.gatech.edu/gvu/ii/citevis/, a tool/poster associated to the publication: http://vispubdata.org/: A Metadata Collection about IEEE Visualization (VIS) Publications.

Assorted collaboration networks contain Categorical nodes directededges, and Dynamicgraphs.

Originally found at: https://www.cc.gatech.edu/gvu/ii/citevis/ https://sites.google.com/site/vispubdata/home?authuser=0 https://dblp.uni-trier.de/ https://github.com/csuvis/MCGS/tree/master/dataset

Download formatted data: GEXF GML GRAPHML JSON

Size: 3503-7102 nodes, 2112-25677 edges

Origin paper:

(Isenberg et al. 2017)

vispubdata.org: A Metadata Collection about IEEE Visualization VIS Publications

(Heymann 2009)

CPAN-explorer

[link]

an interactive exploration of the Perl Ecosystem

Categorical nodes High degree Labeled nodes

Preserving Minority Structures in Graph Sampling

Usage examples:

(Angori et al. 2019)

ChordLink: A New Hybrid Visualization Model0

(Minghim, Paulovich, and Lopes 2006)

Content-based text mapping using multi-dimensional projections for exploration of document collections

Clusters (pre-existing)Dynamic (discrete)Layered graphs N-layers

(Ogawa and Ma 2010)

Software evolution storylines

(Bach, Pietriga, and Fekete 2014)

GraphDiaries: Animated Transitions and Temporal Navigation for Dynamic Networks

Dynamic

(Simonetto, Archambault, and Kobourov 2018)

Drawing Dynamic Graphs Without Timeslices

Dynamic Dynamic (continuous)

(Henry, Fekete, and McGuffin 2007)

NodeTrix: a Hybrid Visualization of Social Networks

Clusters (generated)High degree

(Giacomo et al. 2020)

Storyline Visualizations with Ubiquitous Actors

Clusters (pre-existing)Dynamic Dynamic (discrete)

TimeArcs: Visualizing Fluctuations in Dynamic Networks

(Qu, Zhang, and Zhang 2022)

Automatic Polygon Layout for Primal-Dual Visualization of Hypergraphs

Dynamic Dynamic (discrete)hypergraph Layered graphs N-layers

(Di Bartolomeo, Pister, et al. 2022)

Six methods for transforming layered hypergraphs to apply layered graph layout algorithms

(E. R. Gansner, Hu, and North 2013)

A Maxent-Stress Model for Graph Layout

Preserving Minority Structures in Graph Sampling

Dynamic Dynamic (continuous)Large

Fast filtering and animation of large dynamic networks

(Mizuno et al. 2019)

Optimizing Stepwise Animation in Dynamic Set Diagrams

Clusters (pre-existing)Dynamic Dynamic (discrete)

A Random Sampling O

(A. Arleo, Miksch, and Archambault 2022)

Event-based Dynamic Graph Drawing without the Agonizing Pain

Dynamic (discrete)

(M. Burch et al. 2011)

Parallel Edge Splatting for Scalable Dynamic Graph Visualization

Dynamic Layered graphs N-layers Weighted edges

(Lin et al. 2010)

ContexTour: Contextual Contour Visual Analysis on Dynamic Multi- Relational Clustering

Clusters (generated)Dynamic Dynamic (continuous)Tripartite

(Saket, Scheidegger, and Kobourov 2016)

Comparing Node-Link and Node-Link-Group Visualizations From An Enjoyment Perspective

Clusters (pre-existing)

Statistics

Description from papers

From “Drawing Dynamic Graphs Without Timeslices”

InfoVis Co-Authorship (Discrete): a co-authorship network for papers published in the InfoVis conference from 1995 to 2015 [1]. Authors collaborating on a paper are connected in a clique at the time of publication of the paper. Note this is not a cumulative network as authors can appear, disappear, and appear again. The data is of discrete nature with exactly 21 timeslices (one per year).

From “Event-based Dynamic Graph Drawing without the Agonizing Pain”

InfoVis is a co-authorship network for papers published in the InfoVis conference from 1995 to 2015 [IHK*16]. Authors on a paper are connected in a clique at the time of publication. This is not a cumulative network as authors can appear, disappear and appear again. The dataset has 21 timeslices (one per year).

Example Figures

From “Six methods for transforming layered hypergraphs to apply layered graph layout algorithms”

Fig. 7. Collaborations in papers published at VIS between a set of universities—in particular, these are the collaborators of Harvard University and the collaborators of the collaborators (up to 2 degrees of separation). This figure shows the result of the application of aggregate-collapse.

From “TimeArcs: Visualizing Fluctuations in Dynamic Networks”

Figure 5. The TimeArcs visualization applied to the IEEE VIS publication co-authorship network of the top 50 researchers from 2010 to 2014 (i.e., the same data in Fig. 4).

CPAN Graph Dataset

Descriptions from Literature

From Preserving Minority Structures in Graph Sampling

6.3.2 Cpan Graph Data Set The Cpan data set is a collaboration network with 839 nodes and 2,127 edges [1]. It depicts the relationships between the developers using the same Perl modules. The original graph and samples obtained by FF, TIES, and MCGS are shown in Figure 6. This case focused on the preservation of parachute-like rims at marginal areas.

Example Figures

From Preserving Minority Structures in Graph Sampling

Fig. 6. Visual illustration of the cpan graph data set (a) and three samples generated by ff (b), ties (c), and mcgs (d) with a sampling rate of 30%.

DBLP

Descriptions from the Literature

From ChordLink: A New Hybrid Visualization Model

The second case study considers co-authorship networks extracted from the DBLP dataset [30], which contains publication data in computer science. Through a query consisting of keywords and Boolean operators, one can retrieve a set of publications on a desired topic. We use the results returned by DBLP to construct networks where nodes are authors and edges indicate co-authorships, weighted by the number of papers shared by their end-nodes. Nodes are labeled with authors’ names and edges with the titles of the corresponding publications. We performed the query “network AND visualization” and limited to 500 the number of search results (i.e., publications) to be returned. The resulting network consists of 1766 nodes, 3780 edges, and 382 connected components. The largest of these components contains 118 nodes and 322 edges.

Example Figures

From Parallel Edge Splatting for Scalable dynamic Graph Visualization

Fig. 8. The evolution of the word graph generated from paper titles containing the words “vis” and “web”. 21 graphs are shown for the years 1990 until 2010. A total of 264, 311 edges with weights of more than five are displayed.

From ChordLink: A New Hybrid Visualization Model

Fig. 1. A CHORDLINK visualization of a co-authorship network. The drawing has four clusters, represented as chord diagrams. In each chord diagram, circular arcs of the same color are copies of the same author. For example, in the smallest cluster, F. Montecchiani has two (green) copies, each connected to some nodes external to the cluster.

From Automatic Polygon Layout for Primal-Dual Visualization of Hypergraphs

Fig. 10. Paper and authorship data from the online database DBLP [26] for publications from 2013 to 2015 in IEEE Transactions on Pattern Analysis and Machine Intelligence. Each N-ary relationship is either a paper with N authors (left: the primal view) or an author with N papers (right: the dual view).

Airlines, Migrations, and Air Traffic

Airlines, migrations and air traffic data can be interesting for its Spatialproperties and Directed edges The data is often used for edge bundling algorithms, which group edges together to reduce visual clutter.

The data below was collected from the Edge-Path bundling paper by Markus Wallinger et al. They cite the Airlines dataset to Force Directed Edge Bundling for Graph Visualization and the migrations dataset to Geometry-Based Edge Clustering for Graph Visualization.

Originally found at: https://github.com/mwallinger-tu/edge-path-bundling/tree/master/data

Download formatted data: GEXF GML GRAPHML JSON

Size: 235-1702 nodes, 2101-16494 edges

Number of Graphs: 3

Origin paper:

(Danny Holten and Van Wijk 2009)

Force-Directed Edge Bundling for Graph Visualization

(Cui et al. 2008)

Geometry-Based Edge Clustering for Graph Visualization

Clusters (generated)Dynamic Spatial

Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach

Usage examples:

(Ersoy et al. 2011)

Skeleton-Based Edge Bundling for Graph Visualization

Generic Spatial

(Danny Holten and Wijk 2009)

Force-directed edge bundling for graph visualization

Spatial

(Landesberger et al. 2016)

MobilityGraphs: Visual Analysis of Mass Mobility Dynamics via Spatio-Temporal Graphs and Clustering

(Cui et al. 2008)

Geometry-Based Edge Clustering for Graph Visualization

bundled edges (generated)Generic

(J. Wu et al. 2018)

MLSEB: Edge Bundling Using Moving Least Squares Approximation

(Perri and Scholtes 2020)

HOTVis: Higher-Order Time-Aware Visualisation of Dynamic Graphs

Dynamic Dynamic (discrete)

Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach

(Wang et al. 2020)

Interactive Structure-aware Blending of Diverse Edge Bundling Visualizations

bundled edges (generated)Directed edges Spatial

(Wallinger et al. 2023)

Faster Edge-Path Bundling through Graph Spanners

Statistics

Descriptions from Literature

From “Skeleton-Based Edge Bundling for Graph Visualization”:

Figure 7 illustrates the SBEB and compares it with several existing bundling methods. Note that in all images here generated with our method, we used simple additive edge blending only, as our focus here is the layout, not the rendering. Images (a,b) show an air traffic graph (nodes are city locations, edges are interconnecting flights)… Images (e-h) show the US migrations graph bundled with the WR, GBEB, FDEB, and our method (SBEB) respectively. Overall, SBEB produces stronger bundling, due to the many iterations I = 10 being used), and emphasizes the structure of connections between groups of close cities (due to the skeleton layout cues). If less bundling is desired, fewer iterations can be used (Fig. 4). Adjusting the postprocessing smoothing and relaxation parameters, SBEB can create bundling styles similar to either GBEB (higher bundle curvatures, more emphasis on the graph structure) or FDEB (smoother bundles). Finally, images (i,j) show the US airlines graph bundled with the FDEB and SBEB respectively. SBEB generates stronger bundling (more overdraw) but arguably less clutter. Note also that SBEB generates treelike bundle structures which is useful when the exploration task at hand has an inherent (local) hierarchical nature, e.g. see how traffic connections merge into and/or split from main traffic routes.

Example Figures

From “Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach”:

Fig. 1. Edge bundling of the migrations dataset. (a) Straight line drawing. (b) Force-directed edge bundling aggregates edges well, but overaggregates at the centre of the drawing making it difficult to see patterns in the east-west flow (red bundle). (c) Cubu has a similar drawback at the centre of the map to a lesser degree. (d) Winding roads divides this structure into several smaller flows, but they may not be necessarily related to graph structure. (e) Edge-path bundling is able to distinguish between several flows that reflect paths in the underlying graph. (f) When edge direction is considered, the algorithm is able to further subdivide these flows based on direction.

Fig. 8. Airlines (undirected). (a) Input drawing. (b) Force-directed bundling is able to cluster edges into the major flows, but some overaggregation prevents details from being visualised. (c) Cubu provides a good bundling, but also has overaggregation. (c) Confluent drawings can be imposed on the layout, but as the approach cannot layout the graph bicliques can be distantly located, resulting in suboptimal performance. (e) Winding roads divides the flows into many streams, but these streams can be unfaithful to graph structure. (f) Edge-path bundling aggregates edges using weighted paths. The four prominent bundle intersections on the east coast correspond to major airports: Atlanta, Detroit, Minneapolis, and Dallas.

Fig. 10. Results of four algorithms on the air traffic network. (a) Force-directed bundling is able to recover the major trajectories but does not strongly bundle the network. (b) Cubu strongly bundles the main flows of airtraffic, but can suffer from overaggregation. (c) Winding roads divides the traffic into many smaller bundles, but this may not be reflective of underlying graph structure. (d) With edge-path bundling, each bundle necessarily reflects a path in the network. There are separate flows across the atlantic and asia that correspond to paths through the network.

From “Skeleton-Based Edge Bundling for Graph Visualization”:

Code Dependency Graphs

Various software call dependency graphs have been used in the literature. We provide the benchmarks used in A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts, as these posed the most comprehensive and available collection. Parallel Edge Splatting for Scalable Dynamic Graph Visualization used a software call graph from a device called a “Phillips Medical System Eindhoven medical scanner”, which is lost. Python and Eclipse subversion control logs are also currently lost. The authors of Parallel Edge Splatting for Scalable Dynamic Graph Visualization used https://depfind.sourceforge.io/ to extract the commit history.

Originally found at: http://vis.cs.ucdavis.edu/~ogawa/datasets/ (broken) https://osf.io/dcz5h

Download formatted data: GEXF GML GRAPHML JSON

Size: 128-2956 nodes, 310-10845 edges

Number of Graphs: 11

Origin paper:

(Gove 2019)

A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts

Usage examples:

(M. Burch et al. 2011)

Parallel Edge Splatting for Scalable Dynamic Graph Visualization

Dynamic Layered graphs N-layers Weighted edges

(D. Holten 2006)

Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data

bundled edges (generated)Compound graphs Hierarchical

An Efficient Framework for Generating Storyline Visualizations from Streaming Data

From Parallel Edge Splatting for Scalable Dynamic Graph Visualization:

(Devkota and Isaacs 2018)

CFGExplorer: Designing a Visual Control Flow Analytics System around Basic Program Analysis Operations

Layered graphs N-layers

Statistics

Software Dependency Calls

Descriptions from Literature

From “A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts”:

The software graphs show dependencies in several software packages [vB11, vB02, vB12, vBB13, vvBB14].

From “Parallel Edge Splatting for Scalable Dynamic Graph Visualization”:

We collected the 21 available releases of JUnit as compiled Java bytecode and extracted the method call dependencies using DependencyFinder (depfind. sourceforge.net). The package and class structure provides a natural hierarchy on the methods of the system. The resulting dynamic graph consists of 2,817 vertices connected by 15,339 edges, where each edge is weighted by 1.

Example Figures

Fig. 6. Call dependencies between methods in 21 releases of the JUnit project: all (top), added (left), and removed (right) dependencies.

Phillips Medical Software Call Graph (Lost)

Descriptions from Literature

From “Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data”:

The software is part of a medical scanner and was provided by Philips Medical Systems Eindhoven. Three hierarchy levels – layers, units, and modules – consisting of 284 nodes are used together with the associated call graph for the elements at the lowest level of the hierarchy, i.e., 1,011 adjacency relations representing module-to-module calls.

Example Figures

From “Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data”:

Fig. 13. A software system and its associated call graph (caller = green, callee = red). (a) and (b) show the system with bundling strength β = 0.85 using a balloon layout (node labels disabled) and a radial layout, respectively. Bundling reduces visual clutter, making it easier to perceive the actual connections than when compared to the non-bundled versions (figures 2a and 11a). Bundled visualizations also show relations between sparsely connected systems more clearly (encircled regions); these are almost completely obscured in the non-bundled versions. The encircled regions highlight identical parts of the system for (a), (b), and figure 15.

Subversion Control Logs (Lost)

From “An Efficient Framework for Generating Storyline Visualizations from Streaming Data”:

The datasets we used for this study were: … Python Subversion Control Logs (Python) [30] Eclipse Subversion Control Logs (Eclipse) [30] … These datasets all contained temporal logs of events in which entities interact.

Blogposts, Tweets, and Forums

In the surveyed papers we found various instances of blogposts, tweets, and forum posts. Many of these are timestamped posts that connect user mentions, textually derived entities, hashtags, or user actions on posts. We provide a selection of Blogposts, Tweets, and MOOC (a student forum) as found in the literature. Time Arcs uses AMERICAblog, Huffington Post, and other sources (corpus_ner_geo) data which can be found at https://github.com/CreativeCodingLab/TimeArcs/tree/master/Text/data.

Fast filtering uses the Twitter gardenhouse streaming API to collect data on the 2013 Super Bowl and the announcement of Osama Bin Laden’s death, both can be found https://github.com/WICI/fastviz/tree/master/data (shared hashtags).

Event-based Dynamic Graph Drawing without the Agonizing Pain uses the rugby tweet dataset (pro12_mentions) consisting of mentions among the members of the GuinessPro12 competition, and the MOOC dataset from the KDD Cup 2015 (A data challenge).

This kind of data can be interesting because it might be interpreted as hypergraphdata, where nodes are connected by multiple edges, or as Dynamicdata, where the edges change over time.

Originally found at: http://moocdata.cn/data/user-activity https://github.com/CreativeCodingLab/TimeArcs https://github.com/WICI/fastviz/tree/master/data

Download formatted data: GEXF GML GRAPHML JSON

Size: 12-386412 nodes, 3151-556820 edges

Origin paper:

(Feng et al. 2019)

Understanding Dropouts in MOOCs

TimeArcs: Visualizing Fluctuations in Dynamic Networks

Fast filtering and animation of large dynamic networks

Usage examples:

(Y. Frishman and Tal 2008)

Online Dynamic Graph Drawing

Dynamic

(Purchase et al. 2020)

The Turing Test for Graph Drawing Algorithms

Dynamic Dynamic (continuous)Large

Fast filtering and animation of large dynamic networks

TimeArcs: Visualizing Fluctuations in Dynamic Networks

(A. Arleo, Miksch, and Archambault 2022)

Event-based Dynamic Graph Drawing without the Agonizing Pain

Dynamic (discrete)

Statistics

Blogs/MOOC

Descriptions from Literature

From TimeArcs: Visualizing Fluctuations in Dynamic Networks:

We collected 90,811 political blog posts over a ten-year period from 2005 to 2015 from seven different sources, including AMERICAblog, Huffington Post, and ProPublica. We then ran text analyses on these blogs and generated terms that were classified into four different categories. These terms were then input into TimeArcs.

From Event-based Dynamic Graph Drawing without the Agonizing Pain:

MOOC represents the actions (e.g. viewing a video, submitting an answer, etc.) taken by users on a popular massive open online class platform [KZL19]. The nodes represent users and course activities (targets), and temporal edges represent the actions by users on the targets. We pick and elaborate the first 15 thousands events.

Example Figures

From TimeArcs: Visualizing Fluctuations in Dynamic Networks:

Fig. 7. Overview of political events in the past 10 years using TimeArcs. The top 100 terms were selected based on their sudden attention and degree centrality. Terms are color-coded by category: green for person, red for location, blue for organization, yellow for miscellaneous category.

From Event-based Dynamic Graph Drawing without the Agonizing Pain:

Table 2. Flattened snapshots of the network evolution over time taken at regular intervals. Twenty artificial time slices were inserted for temporal graphs

Tweets

Descriptions from Literature

From Fast filtering and animation of large dynamic networks:

We use data obtained through the Twitter gardenhose streaming API, which covers around 10% of the tweet volume.We focus on two events: the announcement of Osama bin Laden’s death and the 2013 Super Bowl. We consider user mentions and hashtags as entities and their co-occurrence in the same tweet as interactions between them.

From Event-based Dynamic Graph Drawing without the Agonizing Pain:

Rugby is a network derived from over 3000 tweets involving teams in the ‘Guinness Pro12’ rugby competition. The tweets were posted between 1 September 2014 and 23 October 2015. Each tweet contains information about the involved teams and the time of publication with a precision down to the second.

Example Figures

From Fast filtering and animation of large dynamic networks

Social Networks

Various social network datasets are used in the literature and here we provide a collection of some of the ones found in our survey. Namely, the Zachary Karate Club, Facebook100, Infectious SocioPatterns dynamic contact networks, and the Van De Brunt Fraternity Data. Note that Facebook1684 refers to the ego network for user 1684, and this along various other users can be found in SNAP. Unfortunately, we are unable to provide this dataset at this time. Social networks can be useful for their clusteringopportunities and Dynamicproperties.

Originally found at: https://snap.stanford.edu/data/ego-Facebook.html https://cs.swan.ac.uk/~dynnoslice/software.html https://archive.org/details/oxford-2005-facebook-matrix https://osf.io/dcz5h http://www.sociopatterns.org/datasets/infectious-sociopatterns-dynamic-contact-networks/ http://www-personal.umich.edu/~mejn/netdata/

Origin paper:

(Zachary 1977)

An Information Flow Model for Conflict and Fission in Small Groups

(McAuley and Leskovec 2012)

Learning to discover social circles in ego networks

(Isella et al. 2011)

What’s in a crowd? analysis of face-to-face behavioral networks

(Van De Bunt, Van Duijn, and Snijders 1999)

Friendship Networks Through Time: An Actor-Oriented Dynamic Statistical Network Model

(Traud, Mucha, and Porter 2011)

Social Structure of Facebook Networks

(Red et al. 2011)

Comparing Community Structure to Characteristics in Online Collegiate Social Networks

Usage examples:

(Nocaj, Ortmann, and Brandes 2015)

Untangling the Hairballs of Multi-Centered Small-World Online Social Media Networks

Preserving Minority Structures in Graph Sampling

(Simonetto, Archambault, and Kobourov 2018)

Drawing Dynamic Graphs Without Timeslices

Dynamic Dynamic (continuous)

(Raj and Whitaker 2018)

Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs

Clusters (generated)Weighted edges

(Ni et al. 2018)

Network Alignment by Discrete Ollivier-Ricci Flow

(Purchase et al. 2020)

The Turing Test for Graph Drawing Algorithms

An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs

(Qu, Zhang, and Zhang 2022)

Automatic Polygon Layout for Primal-Dual Visualization of Hypergraphs

Clusters (pre-existing)Generic Labeled nodes Layered graphs N-layers

(Hoffswell, Borning, and Heer 2018)

SetCoLa: High-Level Constraints for Graph Layout

A Random Sampling O

(Wang et al. 2019)

Structure-aware Fisheye Views for Efficient Large Graph Exploration

Clusters (pre-existing)Generic Large Spatial

(Wang et al. 2018)

Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization

Clusters (pre-existing)

Zachary Karate Club Dataset

Descriptions from Literature

The Turing Test for Graph Drawing Algorithms describes the dataset simply as “social network” in their Table 1.

From Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs:

The Zachary’s karate club graph is a well known data set that is a social network of friendships in a karate club at a US university, as recorded during a study [32]. This graph contains 34 nodes, each representing an individual, and 78 unweighted edges that represent a friendship between the associated individuals (Fig. 1). During the period of observation, a conflict between two key members, identified as the “administrator” and “instructor”, leads to a split in the club, giving it an interesting two cluster structure. In Fig. 1, nodes representing members who are part of the instructor’s and administrator’s groups are drawn in green and blue, respectively.

Example Figures

From “The Turing Test for Graph Drawing Algorithms”:

Figure from supplementary materials using a force directed layout.

From “Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs”:

Fig. 1. Visualization of Zachary’s karate club social network using (a) MDS, (b) radial layout, and (c) anisotropic radial layout. Node sizes encode betweenness centrality.

****From “Network Alignment by Discrete Ollivier-Ricci Flow”:

Fig. 1. An example of Ricci curvature on the karate club graph before and after Ricci flow. The colors represent the Ricci curvature while the thickness represents the edge weight. Ricci flow deformed the edge weights until Ricci curvatures converged (−0.0027 in this case).

Facebook100

Description from Literature

From Untangling the Hairballs of Multi-Centered, Small-World Online Social Media Networks:

As real world samples, we use the Facebook100 dataset [40], which contains social relations of 100 higher educational institutes in the US. The network size varies from 762 to 41K vertices and from 16K to 1.6M edges. Thedataset is directly from Facebook, not sampled, and thus very complete in terms of capturing the social relations according to a widely used service at that time. Additional attributes obtained from the Facebook profiles are gender, expected year of graduation, dormitory, etc. Due to incomplete profiles, a number of attribute values are missing.

Example Figures

From Untangling the Hairballs of Multi-Centered, Small-World Online Social Media Networks

Fig. 1. Facebook friendships at California Institute of Technology (Caltech36). Vertex color corresponds to dormitory (gray for missing values), but has not been utilized by the layout algorithm. The layout in (a) is based on the entire graph, whereas (b)-(f) use edge embeddedness, which spreads the graph while keeping cohesive groups together. Embeddedness mapped to edge color; backbone edges dark gray.

Facebook Ego Networks (Facebook 1864)

Description from Literature

From ****Preserving Minority Structures in Graph Sampling

The Facebook1684 graph data set is an online social network with 775 nodes and 14,006 edges. The original graph and six samples are shown in Figure 4. This data set is an unbalanced graph in which two large communities include 705 nodes and two small communities/cliques contain only 70 nodes.

The supplemental material for *****Network Alignment by Discrete Ollivier-Ricci Flow* also provides user 1864 of the Facebook ego networks in their repository.

From A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts:

The ego graphs are Facebook ego graphs [ML12] with the ego vertex re-added to the graph.

Example Figures

From Preserving Minority Structures in Graph Sampling](https://ieeexplore.ieee.org/document/9222065)

Fig. 4. Interface for subjective assessment experiment with the Facebook1684 data set (775 nodes and 14,006 edges). The leftmost graph is the original graph. The six randomly arranged samples are generated by SST (a), FF (b), MCGS (c), RW (d), TIES (e), and RDN (f) with a sampling rate of 30%.

Van De Bunt Fraternity

Description from the Literature

From Preserving Minority Structures in Graph Sampling

Van De Bunt (Discrete): shows the relationships between 32 freshmen at seven different time points. A discrete dynamic graph is built using the method of Brandes et al. [9], with an undirected edge inserted into a timeslice if the participants reciprocally report “best friendship” or “friendship” at that time.

Description from the Literature

From SetCoLa: High-Level Constraints for Graph Layout:

Social networks can be a powerful way to understand inter-personal relationships and are useful for tracking the spread of diseases that result from personal contact [RST*98, FHH*01, MRV*03, FHD*11]. The ability to track and identify at risk individuals can lead to treatment and help manage the spread of the disease. In addition to the links between individuals, structuring the layout by node properties such as the social or ethnographically-identified group may reveal additional details about how the disease is spread.

Example Figures

From SetCoLa: High-Level Constraints for Graph Layout:

Fig. 4. The layout for the syphilis social network from (a) Rothenberg et al. [RST*98]. (b) We recreated and improved the layout in SetCoLa by introducing additional padding, alignment, and circle constraints to further highlight the relative number of interactions among the different groups. For both figures, the nodes are split into three groups, from left to right: young affluent white men, younger white women, and young African-American men. Individuals not associated with any of these “core” groups are positioned above the others. In both figures, individuals diagnosed with syphilis during the outbreak are labeled with an “S” on the node label.

Transportation Networks

Transportation networks are interesting because of their Spatialnature, and feautre Directed edges DIMACS USA Road Network source notes that the data has errors, namely missing major highways and bridges. We currently include only the subway layout networks in our files.

Originally found at: http://www.diag.uniroma1.it//challenge9/download.shtml https://osf.io/dcz5h

Download formatted data: GEXF GML GRAPHML JSON

Size: 82-433 nodes, 158-950 edges

Number of Graphs: 15

Origin paper:

(Gove 2019)

A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts

Usage examples:

(Muelder and Ma 2008b)

A Treemap Based Method for Rapid Layout of Large Graphs

Clusters (generated)Generic Large

Rapid Graph Layout Using Space Filling Curves

Compound graphs Directed edges Hierarchical Spatial Weighted edges

(Meulemans et al. 2013)

KelpFusion: A Hybrid Set Visualization Technique

Spatial

(Nollenburg and Wolff 2011)

Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming

Labeled nodes Spatial

(Huang et al. 2016)

TrajGraph: A Graph-Based Visual Analytics Approach to Studying Urban Network Centralities Using Taxi Trajectory Data

Labeled nodes Spatial

(Greilich, Burch, and Diehl 2009)

Visualizing the evolution of compound digraphs with TimeArcTrees

(Brandes and Wagner 1998)

Using Graph Layout to Visualize Train Interconnection Data

Generic Spatial

(Zeng et al. 2019)

Route-Aware Edge Bundling for Visualizing Origin-Destination Trails in Urban Traffic

Categorical nodes Generic Topological Trees Weighted edges

A Random Sampling O

(Preiner et al. 2020)

Augmenting Node-Link Diagrams with Topographic Attribute Maps

(Bast, Brosi, and Storandt 2020)

Metro Maps on Octilinear Grid Graphs

Octilinear Port constraints Terminals

(Zheng, Pawar, and Goodman 2019)

Graph Drawing by Stochastic Gradient Descent

Clusters (pre-existing)Generic Large Spatial

(Wang et al. 2019)

Structure-aware Fisheye Views for Efficient Large Graph Exploration

(Wang et al. 2018)

Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization

Clusters (pre-existing)

(Batik et al. 2022)

Shape-Guided Mixed Metro Map Layout

Categorical nodes

Subways

Statistics

Description from Literature

Apart from the example of Sydney presented in Section 6, we have evaluated our method for two additional real-world networks: Vienna, which is a rather small network, and London, the oldest and still one of the most complex metro systems in the world. These networks have not been used as examples for previous metro map layout methods, so we can compare only against the official maps of Vienna and London. The size of the metro graphs (including Sydney) is given in Table 3 and ranges from 84 vertices and 8 faces (Vienna) to 308 vertices and 55 faces (London). The table further shows how the removal of degree-2 vertices described in Section 5.1 effectively reduces the number of vertices and edges.

Example Figures

From “Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming”:

Fig. 16. Unlabeled layout of the London Underground network produced by our method.

DIMACS USA Road Networks

Description from Literature

From “A Treemap Based Method for Rapid Layout of Large Graphs”:

The other graphs used in this paper are: a graph of network scans, which is a complete graph with edge weights between 0 and 1, but for clarity, edges with weights less than a certain threshold are not shown (Figures 3 and 4, |V|=878,|E|=385003, [19]), a small artificial graph of a grid topology (Figure 5, |V|=16,|E|=24), a large graph of streets in the San Francisco Bay Area (Figure 7, |V|=321,270,|E|=800,172, [8]).

From “Rapid Graph Layout Using Space Filling Curves”:

Finally, the “usafla” dataset (shown in Figure 7) is of the intersections and the streets between them in the state of Florida

Example Figures

From “A Treemap Based Method for Rapid Layout of Large Graphs”:

Fig. 7. Scalability. Our approach can scale to very large networks while still maintaining interactivity. |V|=321,270,|E|=800,172

From “Rapid Graph Layout Using Space Filling Curves”:

Fig. 7. Scalability. Our approach can scale to large graphs. This graph is of the streets in the state of Florida, |V| = 1,070,376,|E| = 2,712,798 One small region is expanded to show detail.

Lost and unavailable datasets

Unfortunately, some of the datasets that were used in the papers in our corpus are lost, or not available anymore. A dataset that is not anymore accessible renders all the papers using it unfortunately not reproducible. Most of the instances we found became lost because of lack of maintenance of the original storage locations: websites, servers, or repositories. This is, unfortunately, a significant issue in science, which is now hopefully gaining more and more attention.

“Loss” of a dataset does not exclusively mean that the entire, original dataset became lost, but also that a paper using a dataset with particular edits—such as interpreting a debate as a graph between the participants—has not documented well enough their process and did not link to the edited dataset. This makes it impossible to reproduce the results of the paper, and is further discussed in Section 4.1.6.

While we did go through the effort, for each one of them, to recover them and store them on OSF, we could not find anywhere the following list of datasets:

GION

The data was originally collected for a Bioinformatics paper, Graph-based clustering and characterization of repetitive sequences in next-generation sequencing data. It was then used in GION: Interactively Untangling Large Graphs on Wall-Sized Displays as a benchmark for their layout and experiment. However, the links to the original data no longer work. It had Sparse denseand Largegraphs.

Originally found at: http://wcl.ml.unisa.edu.au/graph-untangling/graphs.zip

Number of Graphs: 8

Size: 8 graphs, 1159-7885 nodes, 6424-427406 edges

Origin paper:

(Marner et al. 2014)

GION: Interactively Untangling Large Graphs on Wall-Sized Displays

(Novák, Neumann, and Macas 2010)

Graph-based clustering and characterization of repetitive sequences in next-generation sequencing data

Usage examples:

Drawing Big Graphs Using Spectral Sparsification

(Marner et al. 2014)

GION: Interactively Untangling Large Graphs on Wall-Sized Displays

Descriptions from Literature

From “Drawing Big Graphs Using Spectral Sparsification”:

this consists of RNA sequence graphs that are used for the analysis of repetitive sequences in sequencing data; these graphs have been used in previous experiments. They are locally dense and globally sparse, and generally have distinctive shapes.

From “GION: Interactively Untangling Large Graphs on Wall-Sized Displays”:

We selected graphs that come from a real world application where graph visualization is used for data analysis and the graph size and layout quality requirements pose a challenge for state-of-the-art layout methods. Our graph set consists of RNA sequence graphs that are used for the analysis of repetitive sequences in sequencing data [11].

Graph properties are provided in Table 1. The set of graphs can be downloaded from http://wcl.ml.unisa.edu.au/graph-untangling/graphs.zip. All graphs have high local density, and a sparse global structure that allows to create layouts far from hairballs that are showing the structure well.

Example Figures

From “GION: Interactively Untangling Large Graphs on Wall-Sized Displays”:

From “Graph-based clustering and characterization of repetitive sequences in next-generation sequencing data”:

Fig. 4. Examples of graph layouts derived from clusters of repetitive sequences. Graph layouts were calculated using the 3D version of Fruchterman and Reingold algorithm from which a 2D projection is shown. Individual reads are represented by vertices and similar reads are connected by edges. Individual clusters are described further in Table 1.

FM3

FM3 contains trees, path graphs, cycle graphs, scale-free graphs, caterpillar graphs, planar graphs, and generic graphs (connected simple graphs, generated with uniform probability distribution). Nonetheless, download links to data are broken.

Originally found at: http://www.felicedeluca.com/ply/data.html (broken)

Origin paper:

(De Luca et al. 2017)

An Experimental Study on the Ply Number of Straight-Line Drawings”

Usage examples:

(Heinsohn and Kaufmann 2018)

An Interactive Tool to Explore and Improve the Ply Number of Drawings