# 1 Transportation Networks

Note: 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. graph features handled: Directed edges, Spatial Graph features in papers: clusters (generated),generic,large,generic,large,spatial,labeled nodes,spatial,compound graphs,directed edges,hierarchical,spatial,weighted edges,generic,spatial,bundled edges (generated),spatial,generic,categorical nodes,generic,topological,trees,weighted edges,octilinear,port constraints,terminals,clusters (pre-existing),generic,large,spatial,clusters (pre-existing),categorical nodes Origin Paper: A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts (https://www.notion.so/A-Random-Sampling-O-n-Force-calculation-Algorithm-for-Graph-Layouts-a0bc2ae6ebdb4e8cbddb924c0484cfad?pvs=21) Originally found at: http://www.diag.uniroma1.it//challenge9/download.shtml https://osf.io/dcz5h Size: 82-433 nodes, 158-950 edges Number of Graphs: 15 Appeared in years: 2008,2013,2011,2016,2009,1998,2019,2020,2018,2022 Type of Collection: Aggregate collection is it stored properly?: No must be analyzed: No In repo?: No Related to Literature - Algorithm (1) (Dataset tag relations): KelpFusion: A Hybrid Set Visualization Technique (https://www.notion.so/KelpFusion-A-Hybrid-Set-Visualization-Technique-145828a44b7a437eb633075383f7cede?pvs=21), TrajGraph: A Graph-Based Visual Analytics Approach to Studying Urban Network Centralities Using Taxi Trajectory Data (https://www.notion.so/TrajGraph-A-Graph-Based-Visual-Analytics-Approach-to-Studying-Urban-Network-Centralities-Using-Taxi-21e339918ee44f5da7703535881936f8?pvs=21), Visualizing the evolution of compound digraphs with TimeArcTrees (https://www.notion.so/Visualizing-the-evolution-of-compound-digraphs-with-TimeArcTrees-2431c9f6f9c5440589c57f9a723b3ac4?pvs=21), Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming (https://www.notion.so/Drawing-and-Labeling-High-Quality-Metro-Maps-by-Mixed-Integer-Programming-5a4b255a5dbd4f18a7f88d70212a2eff?pvs=21), A Treemap Based Method for Rapid Layout of Large Graphs (https://www.notion.so/A-Treemap-Based-Method-for-Rapid-Layout-of-Large-Graphs-7d9e14d48d9e452da4fcf8b64b007ea5?pvs=21), Rapid Graph Layout Using Space Filling Curves (https://www.notion.so/Rapid-Graph-Layout-Using-Space-Filling-Curves-847c46047b5c400bb9dcf339c8d42f12?pvs=21), Using Graph Layout to Visualize Train Interconnection Data (https://www.notion.so/Using-Graph-Layout-to-Visualize-Train-Interconnection-Data-b96db45ca8e94e75bf9a65ee15658ebf?pvs=21) cleaned format?: No duplicate?: No link works?: No Added in paper: No OSF link json: https://files.osf.io/v1/resources/j7ucv/providers/osfstorage/64d90f1394a6be0ec012e916 Origin paper plaintext: A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts Page id: 720a658bb1914b51910c480d86943e80 unavailable/skip: No Cleaned ALL data: No OSF link gexf: https://files.osf.io/v1/resources/j7ucv/providers/osfstorage/64d9498894a6be103212e712 OSF link gml: https://files.osf.io/v1/resources/j7ucv/providers/osfstorage/64d94d990c2b4d0e9c386231 OSF link graphml: https://files.osf.io/v1/resources/j7ucv/providers/osfstorage/64d970f894a6be112a12ea21 first look: No sparkline data: {‘min’: 82, ‘max’: 433, ‘step_size’: 25, ‘num_bins’: 18, ‘bins’: [0, 25, 50, 75, 100, 125, 150, 175, 200, 225, 250, 275, 300, 325, 350, 375, 400, 425], ‘num_nodes’: [0, 0, 0, 1, 2, 5, 1, 0, 2, 0, 1, 1, 0, 0, 0, 1, 0, 1]} Related to Literature - Algorithm (Dataset tag relations) 1: A Treemap Based Method for Rapid Layout of Large Graphs (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/A%20Treemap%20Based%20Method%20for%20Rapid%20Layout%20of%20Large%20G%20f96d2a808a5f4df2a781d9a890e2b266.md), Rapid Graph Layout Using Space Filling Curves (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Rapid%20Graph%20Layout%20Using%20Space%20Filling%20Curves%2010601cd6078a4ea18b17c7d40eda0041.md), KelpFusion: A Hybrid Set Visualization Technique (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/KelpFusion%20A%20Hybrid%20Set%20Visualization%20Technique%2031a567279ecc4c3980caf078144017db.md), Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Drawing%20and%20Labeling%20High-Quality%20Metro%20Maps%20by%20Mi%2096459aa8ab3641978c6a93e1bd4447a2.md), TrajGraph: A Graph-Based Visual Analytics Approach to Studying Urban Network Centralities Using Taxi Trajectory Data (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/TrajGraph%20A%20Graph-Based%20Visual%20Analytics%20Approach%20%20a8a60bf2c8d34198b967636b64e97be6.md), Visualizing the evolution of compound digraphs with TimeArcTrees (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Visualizing%20the%20evolution%20of%20compound%20digraphs%20wit%20e3c6f596c3644af2a9be28dd3f7d57c5.md), Using Graph Layout to Visualize Train Interconnection Data (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Using%20Graph%20Layout%20to%20Visualize%20Train%20Interconnect%20d1e747efa23d469496dc7e73249d49d9.md), Route-Aware Edge Bundling for Visualizing Origin-Destination Trails in Urban Traffic (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Route-Aware%20Edge%20Bundling%20for%20Visualizing%20Origin-D%2063f378f25262476cbf983d569ca1af95.md), A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/A%20Random%20Sampling%20O(n)%20Force-calculation%20Algorithm%2086599a831f314d1cb8871a5a92420d0f.md), Augmenting Node-Link Diagrams with Topographic Attribute Maps (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Augmenting%20Node-Link%20Diagrams%20with%20Topographic%20Att%205995a73c463c49db8ee966cc9db41ec5.md), Metro Maps on Octilinear Grid Graphs (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Metro%20Maps%20on%20Octilinear%20Grid%20Graphs%20a8834ec2af3f40aab051ef1bfb5ddb1a.md), Graph Drawing by Stochastic Gradient Descent (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Graph%20Drawing%20by%20Stochastic%20Gradient%20Descent%20c829549f150044628d68b79584273c19.md), Structure-aware Fisheye Views for Efficient Large Graph Exploration (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Structure-aware%20Fisheye%20Views%20for%20Efficient%20Large%20%20690c77bbfc7647c098c21827e4491457.md), Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Revisiting%20Stress%20Majorization%20as%20a%20Unified%20Framew%200765ea891e9e403593025430656f35f3.md), Shape-Guided Mixed Metro Map Layout (../Benchmark%20sets%200cc6b5e454304aec98f3b59b1a720476/Literature%20ad87f14e7097454fb2f784e2c8a2797a/Literature%20-%20Algorithm%2012e01bfc60a84007aa7d2d34293e123d/Shape-Guided%20Mixed%20Metro%20Map%20Layout%20e1bb181a68304d8bac8dd8167081c028.md)

# 2 Body

## 2.1 Subways

### Statistics

four_in_one.svg

### 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.

Untitled

### Example Figures

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

Untitled

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

## 2.2 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”:

Untitled

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”:

Untitled

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.

=== STOP RENDERING ===

http://www.diag.uniroma1.it//challenge9/download.shtml