Fast and Compact Planar Embeddings

Leo Ferres, José Fuentes-Sepúlveda, Travis Gagie, Meng He, and Gonzalo Navarro

Introduction

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.

PDF document

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

The code

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.

Experiments

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.

All the datasets are available here.

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.

Results

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.