Planar graphs

In this page we provide several undirected planar graphs, each one with a planar embedding. Any planar graph with n vertices has m < 3n-6 edges.

To read the datasets and create new ones, please, use the following this code.

Format of the datasets

Each dataset has the following format:

For each vertex v, the edges of v are listed in counterclockwise order. All the vertices are identified by an index. All the indices belongs to the range [0,n-1], where n is the number of vertices of the graph. Below, there is an example of the format.

Graph:

Format:

5
7
0 1
0 2
0 3
0 4
1 0
1 4
1 2
2 0
2 1
3 0
3 4
4 0
4 3
4 1

Each dataset was generated in three stages: In the first stage, we used the function rnorm of R to generate random coordinates (x,y) (with mean 0 and standard deviation 10,000). The only exception was the dataset World cities, which corresponds to the coordinates of 2,243,467 uniques cities in the world. In the second stage, we generated the Delaunay Triangulation of the coordinates generated in the first stage. The triangulations were generated using Triangle (with options -cezCBVPNE), a piece of software dedicated to the generation of meshes and triangulations. In the third stage, we generated planar embeddings of the Delaunay triangulations computed in the second stage. The planar embedding was generated with the The Edge Addition Planarity Suite (with options -s -q -p). Note: For the dataset Planar-16M the random coordinates follow a Zipf distribution.

Additionally, we provide datasets of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. The TIGER dataset provides geographic and cartographic information of the administrative divisions of the territory in USA. The information is hierarchically organized in granularity levels. During the construction of the datasets, we found cases where a region was composed of disconnected subregions (e.g. Santa Catalina Island is a disconnected region of the State of California). In such cases, we only considered the largest subregion. Similarly, we did not consider Alaska, Hawaii and overseas U.S. islands. The TIGER dataset has a limited number of regions composed of non-contiguous sub-regions. For instance, the number of faces is 19,785,187 and we filtered out the 49,313 faces that are non-contiguous, which is quite small (0.25%).