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.