Graph:

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.

Each dataset has the following format:

<Number of vertices>

<Number of edges>

<Source vertex> <Target vertex>

<Source vertex> <Target vertex>

<Source vertex> <Target vertex>

...

<Number of edges>

<Source vertex> <Target vertex>

<Source vertex> <Target vertex>

<Source vertex> <Target vertex>

...

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

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

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%).

A planar graph with 1,000,000 vertices and 2,999,978 edges. The embedding of the graph is planar.

A planar graph with 5,000,000 vertices and 14,999,983 edges. The embedding of the graph is planar.

A planar graph with 10,000,000 vertices and 29,999,979 edges. The embedding of the graph is planar.

A planar graph with 15,000,000 vertices and 44,999,983 edges. The embedding of the graph is planar.

A planar graph with 20,000,000 vertices and 59,999,975 edges. The embedding of the graph is planar.

A planar graph with 25,000,000 vertices and 74,999,979 edges. The embedding of the graph is planar.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. It corresponds to the state of Alaska, with a total of 93,366 vertices, 213,842 edges and 50 connected components. This dataset consider five aggregation levels: states, counties, census tracts, census block groups and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. It corresponds to the state of Hawaii, with a total of 33,558 vertices, 80,882 edges and 17 connected components. This dataset consider five aggregation levels: states, counties, census tracts, census block groups and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. It corresponds to American Samoa, Guam, Commonwealth of the Northern Mariana Islands, Puerto Rico and U.S. Virgin Islands, with a total of 125,091 vertices, 305,877 edges and 22 connected components. This dataset consider five aggregation levels: states, counties, census tracts, census block groups and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. The dataset consists of 19,738,992 vertices and 43,844,286 edges. It is the result of filtering the largest connected components of the geographic faces, considering three aggregation levels: states, counties and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. The dataset consists of 19,737,531 vertices and 43,840,815 edges. It is the result of filtering the largest connected components of the geographic faces, considering four aggregation levels: states, counties, census block groups and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. The dataset consists of 19,735,874 vertices and 43,837,150 edges. It is the result of filtering the largest connected components of the geographic faces, considering five aggregation levels: states, counties, census tracts, census block groups and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. The dataset consists of 19,785,187 vertices, 43,903,023 edges and 9 connected components. It corresponds to the continental U.S.A., except Alaska. This dataset consider five aggregation levels: states, counties, census tracts, census block groups and census blocks. Additional information about the aggregation levels is available here.

Dataset of geographic faces from the dataset TIGER, provided by the U.S. Census Bureau. The dataset consists of 20,037,199 vertices, 44,503,624 edges and 98 connected components. It corresponds to the whole map of U.S.A., including Alaska, Hawaii and other overseas islands. This dataset consider five aggregation levels: states, counties, census tracts, census block groups and census blocks. Additional information about the aggregation levels is available here.

A triangulated planar graph with 2,243,467 vertices and 6,730,395
edges. The embedding of the graph is planar. Each vertex corresponds to
the coordinate *(lat,lon)* of a city. The list of cities is
available at
~~
https://www.maxmind.com/en/free-world-cities-database~~
https://dspace-cris.4science.it/handle/123456789/31. The
original dataset contains 3,173,959 cities, but some of them have
the same coordinates. We selected the 2,243,467 cities with unique
coordinates to build our dataset worldcities.