The triangulated plane graphs have been used to represent polytopes, geographic maps, microchip layouts and design, software engineering diagrams, surface meshes in computer graphics, among others. In practice, triangulated plane graphs may be large, such as in VLSI (very large scale integrations) circuits or TIN (triangulated irregular network) surfaces. Thus, the design of space-efficient representations of triangulated plane graph becomes useful.

A graph $G=\left(V,E\right)$, with $\left|V\right|=n$ vertices, $\left|E\right|=m$ edges and $f$ faces, is a triangulated planar graph if $G$ is planar and the addition of any edge to $G$ results in a nonplanar graph. A triangulated planar graph with a particular drawing or embedding is a triangulated plane graph. Triangulated plane graphs are also known as maximal plane graphs. Notice that a triangulated plane graph with $n$ vertices has $3n-6$ edges, $2n-4$ faces and all its faces are triangles.

A common approach to construct succinct representations of triangulated
plane graphs is to decompose them into a set of trees and subgraphs,
representing them as parentheses sequences to then apply some ideas of
succinct ordinal trees to support operations in optimal time. Operations of
interest are the computation of the degree of a vertex (*degree*) and the
adjacency test of two vertices (*adjacency*). Usually, decomposition is
achieved using either *canonical ordering* [1, 2, 3, 4], *realizers* [5,
6] and *orderly spanning trees* [7]. In [8], authors show that canonical
orderings, realizers and orderly spanning trees are equivalent on
triangulated plane graphs. We adopt the canonical ordering approach, but
extend our results to realizers which support more operations.

In this work, we provide a parallel algorithm to construct succinct representations of triangulated plane graphs given its canonical ordering. Additionally, we adapt our algorithm to compute succinct representations based on realizers.

The code for this work is available at github.

- worldcities: A triangulated plane graph with 2,243,467 nodes and 6,730,395 edges (max. fan-out: 36, min. fan-out: 3).
- rand-1M: A triangulated plane graph with 1,000,000 nodes and 2,999,994 edges (max. fan-out: 20, min. fan-out: 3).
- rand-2M: A triangulated plane graph with 2,000,000 nodes and 5,999,994 edges (max. fan-out: 14, min. fan-out: 3).
- rand-4M: A triangulated plane graph with 4,000,000 nodes and 11,999,994 edges (max. fan-out: 18, min. fan-out: 3).
- rand-8M: A triangulated plane graph with 8,000,000 nodes and 23,999,994 edges (max. fan-out: 17, min. fan-out: 3).
- rand-10M: A triangulated plane graph with 10,000,000 nodes and 29,999,994 edges (max. fan-out: 24, min. fan-out: 3).

Each input was generated in four stages: In the first stage, we used the
function rnorm of *R* to generate random
coordinates $\left(x,y\right)$. The
only exception was the dataset worldcities,
which corresponds to the coordinates of 2,243,467 uniques cities in the
world. The dataset containing the coordinates was created by MaxMind,
available here. 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. In the second stage,
we generated the *Delaunay Triangulation* of the coordinates generated in the first stage. The
triangulations were generated
using Triangle,
a piece of software dedicated to the generation of meshes and
triangulations (Our triangulations were generated using the options
-cezCBVPNE.). In the third stage, we generated the maximal plane graph
and the canonical ordering of the Delaunay triangulation computed in the
second stage. Both the graph and the canonical ordering were computed
using the Boost Library. The graph
was generated with the function make_maximal_planar
and the canonical ordering was computed with the
function planar_canonical_ordering. Finally,
in the fourth stage, we generated the canonical spanning tree of each
maximal plane graph. We repeated each experiment five times and recorded
the median time.

The experiments were carried out on a machine with four 16-core AMD Opteron® 6278 processors clocked at 2.4GHz, with 64KB of L1 cache per core, 2MB of L2 cache shared between two cores, and 6MB of L3 cache shared between 8 cores. The machine had 189GB of DDR3 RAM, clocked at 1333MHz. 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.

- [1] Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, and Hsueh-I Lu: Compact encodings of planar graphs via canonical orderings and multiple parentheses. In Automata, Languages and Programming. pp. 118–129. Springer Berlin Heidelberg (1998)
- [2] Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, and Hsueh-I Lu: Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. In CoRR, cs.DS/0102005 (2001)
- [3] Xin He, Ming-Yang Kao, and Hsueh-I Lu: Linear-time succinct encodings of planar graphs via canonical orderings. In SIAM Journal on Discrete Mathematics. 12(3): pp. 317–325 (1999)
- [4] Melanie Badent, Ulrik Brandes, and Sabine Cornelsen: More canonical ordering. In Journal of Graph Algorithms and Applications, 15(1): pp. 97–126 (2011)
- [5] Jérémy Barbay, Luca Castelli Aleardi, Meng He, and J.Ian Munro: Succinct representation of labeled graphs. In Algorithmica, 62(1-2): pp. 224–257 (2012)
- [6] Walter Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’90. pp. 138–148. Philadelphia, PA, USA (1990).
- [7] Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu: Orderly spanning trees with applications. SIAM J. Comput., 34(4): pp. 924–945 (2005)
- [8] Kazuyuki Miura, Machiko Azuma, and Takao Nishizeki: Canonical decomposi- tion, realizer, schnyder labeling and orderly spanning trees of plane graphs. In International Journal of Foundations of Computer Science, 16(01):pp. 117–141 (2005)

This work was supported the doctoral scholarship of CONICYT (21120974) and in part by the Emerging Leaders in the Americas scholarship programme

Contact us at: jfuentess@udec.cl

We would like to thank to
Free DNS and
HighCharts for their services