# Parallel Construction of Triangulated Plane Graphs

José Fuentes-Sepúlveda, Meng He, Leo Ferres and Norbert Zeh

## Introduction

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

The code for this work is available at github.

## Experiments

We implemented the our algorithm in C and compiled it using GCC 4.9 with optimization level -O2 and using the -ffast-math flag. There is not available implementations to construct succinct representations of triangulated plane graphs. Therefore, we compared our parallel algorithm with its sequential version. All parallel code was compiled using the GCC Cilk branch. We tested our algorithm on six inputs:
• 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.

•  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)
•  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)
•  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)
•  Melanie Badent, Ulrik Brandes, and Sabine Cornelsen: More canonical ordering. In Journal of Graph Algorithms and Applications, 15(1): pp. 97–126 (2011)
•  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)
•  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).
•  Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu: Orderly spanning trees with applications. SIAM J. Comput., 34(4): pp. 924–945 (2005)
•  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