# Fast algorithm to embed a triangulation into plane

Let $$G = (V, E)$$ be a planar graph such that $$|E| = 3|V| - 6$$ (so $$G$$ must be a triangulation without Kuratowski subgraphs). Given the adjacent matrix $$A$$ of $$G$$, please design an algorithm to embed $$G$$ into $$\mathbb{R}^2$$. The algorithm should output the 2D coordinate of every vertex $$v \in V$$. The algorithm has to be exact instead of approximate and/or heuristic (eg. annealing).

For example, let $$A = \begin {pmatrix} 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \end {pmatrix}$$ of which the $$0$$-th to $$5$$-th row corresponds to $$a, b, c, d, e, f$$, respectively. Then we can find an embedding:

$$a \rightarrow (0, 1)$$, $$b \rightarrow (-\frac{\sqrt{3}}{2}, -\frac{1}{2})$$, $$c \rightarrow (\frac{\sqrt{3}}{2}, -\frac{1}{2})$$, $$d \rightarrow (-\frac{1}{4}, 0)$$, $$e \rightarrow (\frac{1}{4}, 0)$$, $$f \rightarrow (0, -\frac{1}{4})$$.

Here are what I have tried:

(1) The Demoucron-Malgrange-Pertuiset (DMP) algorithm. However, it seems that DMP algorithm only provides an embedding but not guarantee that each face is a convex triangle.

(2) Tutte's theorem (https://ti.inf.ethz.ch/ew/lehre/GA07/lec-kuratowski.pdf): If G is a 3-connected graph with no Kuratowski subgraph, then G has a convex embedding in the plane with no three vertices on a line. The proof of this theorem (see pdf) is constructive, hence we can formulate an algorithm using it. However, on each step, this proof searches an edge $$e \in E$$ such that $$G \cdot e$$ is also 3-connected, and it takes $$|E|$$ steps to converge, so it runs in $$O(|E|^2)$$ time, which is quite slow for engineering.

(3) Delaunay triangulation (DT). To be honest I am not very familiar with it. It seems that DT only provides a triangulation but cannot embed a concrete graph.

Btw, would you please recommend some softwares for drawing the graph? Thanks! This figure is drawn using the Python package Matplotlib.

Question in CS Stackexchange: https://cs.stackexchange.com/questions/151281/fast-algorithm-to-embed-a-triangulation-into-plane.

Fary's theorem assert's you can find a straight line embedding.
De Fraysseix, Pach and Pollack gave an $$\mathcal{O}(n\log(n))$$ algorithm giving such an embedding on a linear-sized grid [1], [2].
It was improved to linear time by Chrobak, M.; Payne [3].

The advantage of an embedding in a grid is that it avoids extreme precision on the coordinates of the vertices.

[1]: de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica 10, No. 1, 41-51 (1990). ZBL0728.05016.
[2]: de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), "Small sets supporting Fary embeddings of planar graphs", Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433, doi:10.1145/62212.62254, ISBN 0-89791-264-0, S2CID 15230919.
[3]: Chrobak, M.; Payne, T. H., A linear-time algorithm for drawing a planar graph on a grid, Inf. Process. Lett. 54, No. 4, 241-246 (1995). ZBL0875.68452.

• Are there implementations of this embedding (or others) available? Commented Aug 23, 2022 at 16:23
• @LasseRempe I found this: boost.org/doc/libs/1_62_0/libs/graph/doc/… Commented Aug 23, 2022 at 19:44
• Thank you, yes this is useful. The triangulations I want to embed are not maximal, and may also have multiple edges / vertices, and it could be that adding all the additional edges required makes the graph hard to look at, but this would definitely be a start. Thank you! Commented Sep 15, 2022 at 22:08