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

<Number of vertices>
<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

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

## Planar-1M (29 MB)

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

## Planar-5M (156 MB)

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

## Planar-10M (319 MB)

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

## Planar-15M (498 MB)

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

## Planar-20M (671 MB)

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

## Planar-25M (849 MB)

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

## World cities (68 MB)

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