The rate at which we store data is increasing even faster than the speed and capacity of computing hardware. Thus, if we want to use what we store efficiently, we need to represent it in better ways. The surge in the number and complexity of the maps we want to have available on mobile devices is particularly pronounced and has resulted in a bewildering number of ways to store planar graphs. Each of these representations has its disadvantages, however: e.g., some do not support fast navigation, some are large, some cannot represent multi-edges or certain embeddings, and some are complicated to build in practice, especially in parallel, which is a practical concern when dealing with massive datasets.

Turán [1] gave a very simple representation for a specified embedding of a
connected planar multi-graph with *n* vertices and *m* edges that
uses *4m* bits, but Jacobson [2] noted that it "does not allow fast
searching". In this work we show how to add a sublinear number of bits to
Turán's representation such that it supports fast
navigation. Additionally, we present the first linear-work and practical
parallel algorithm for building compact representations of planar
graphs. Also, we present an experimental study of our parallel algorithm,
discussing some practical trade-offs. We provide a set of experiments to
prove the scalabitily and good space-usage of our implementation, using a
small portion of the original input. Finally, we provide implementations of
useful queries that also behave efficiently.

An author's version of our work can be downloaded here.

The code for this work is available at github.

A new version of the code is here. It corresponds to an integration with the library SDSL.

We implemented our construction algorithm in C and compiled it using GCC 5.4 with Cilk Plus extension.

We tested our algorithm on six datasets:

- wc: The planar embedding of
a
*Delaunay Triangulation*of the coordinates of 2,243,467 uniques cities in the world. The coordinates were obtained from the Free World Cities Database. - pe5M: The planar embedding of
a
*Delaunay Triangulation*of 5 millions of random coordinates. - pe10M: The planar embedding of
a
*Delaunay Triangulation*of 10 millions of random coordinates. - pe15M: The planar embedding of
a
*Delaunay Triangulation*of 15 millions of random coordinates. - pe20M: The planar embedding of
a
*Delaunay Triangulation*of 20 millions of random coordinates. - pe25M: The planar embedding of
a
*Delaunay Triangulation*of 25 millions of random coordinates.

The experiments were carried out on a NUMA machine with two NUMA nodes. Each NUMA node includes a 14-core Intel® Xeon® CPU (E5-2695) processor clocked at 2.3GHz. The machine runs Linux 2.6.32-642.el6.x86 64, in 64-bit mode. The machine has per-core L1 and L2 caches of sizes 64KB and 256KB, respectively and a per-processor shared L3 cache of 35MB, with a 768GB DDR3 RAM memory (384GB per NUMA node), clocked at 1867MHz. Hyperthreading was enabled, giving a total of 28 logical cores per NUMA node. Running times were measured using the high-resolution (nanosecond) C functions in time.h. Memory usage was measured using the tools provided by malloc_count.

In the table, seq corresponds to a serialization of our parallel algorithm.

p |
wc |
pe5M |
pe10M |
pe15M |
pe20M |
pe25M |
---|---|---|---|---|---|---|

seq |
5.56 | 13.55 | 27.86 | 42.34 | 57.04 | 71.76 |

1 | 7.08 | 17.14 | 35.63 | 54.21 | 73.11 | 92.17 |

2 | 4.06 | 9.71 | 20.26 | 30.67 | 41.37 | 52.16 |

4 | 2.12 | 4.98 | 10.31 | 15.75 | 21.17 | 26.70 |

8 | 1.13 | 2.65 | 5.36 | 8.25 | 10.81 | 13.61 |

12 | 0.78 | 1.84 | 3.74 | 5.61 | 7.50 | 9.46 |

16 | 0.60 | 1.40 | 2.84 | 4.32 | 5.74 | 7.28 |

20 | 0.49 | 1.15 | 2.33 | 3.57 | 4.65 | 6.02 |

24 | 0.41 | 0.97 | 2.01 | 3.15 | 4.11 | 5.10 |

28 | 0.42 | 1.01 | 2.05 | 3.04 | 3.88 | 5.36 |

32 | 0.38 | 0.90 | 1.85 | 2.82 | 3.77 | 4.80 |

36 | 0.34 | 0.83 | 1.72 | 2.57 | 3.48 | 4.38 |

40 | 0.33 | 0.76 | 1.58 | 2.41 | 3.22 | 4.04 |

44 | 0.31 | 0.71 | 1.47 | 2.23 | 3.01 | 3.72 |

48 | 0.30 | 0.68 | 1.37 | 2.09 | 2.76 | 3.56 |

52 | 0.29 | 0.65 | 1.33 | 2.01 | 2.67 | 3.36 |

56 | 0.31 | 0.61 | 1.24 | 1.90 | 2.54 | 3.35 |

- [1] G. Turán, On the succinct representation of graphs, DAM 8 (1984) 289-294.
- [2] G. Jacobson, Space-efficient static trees and graphs, in: FOCS, 1989, pp. 549-554.

The second and fifth authors received travel funding from EU grant H2020-MSCA-RISE-2015 BIRDS GA No. 690941. The second author received funding from Conicyt Fondecyt 3170534. The third and fifth authors received funding Basal Funds FB0001, Conicyt, Chile. The third author received funding from Academy of Finland grant 268324. Early parts of this work were done while the third author was at the University of Helsinki and while the third and fifth authors were visiting the University of A Coruña.

Contact us at: jfuentess@dcc.uchile.cl