$\newcommand{\N}{\mathbb{N}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{E}$

$\DeclareMathOperator{\deg}{deg}$Tutte’s Theorem states that every internally 3-connected planar graph has a convex drawing and that we can even pick the outer face and the convex polygon that it maps to.

What is the smallest value of $N$ such that every $n$-vertex internally 3-connected planar graph has a convex drawing with its vertices on the $N\times N$ grid?

Let $G$ be an $n$-vertex internally 3-connected planar graph and let $C$ be the outer face of $G$. Tutte’s proof shows that the system of linear equations \[ \left\{ (x_u,y_u) = (1/\deg(u))\sum_{(u,w)\in E(G)}(x_w,y_w) : v\in V(G)\setminus V(C) \right\} \] has a unique solution, after fixing the coordinates of $C$ to be the vertices of a convex polygon. If we take coordinates of $C$ to be positive integers in $O(n)$, then Bareiss’ Algorithm implies that the each of the coordinates obtained by the solution to this system of equations is rational and can be represented using $O(n\log n)$ bits. Multiplying through by the product of the denominators therefore implies that $N\le n^{O(n^2)}$.

Can we improve the preceding argument to show $N\le n^{O(n)}$

$\DeclareMathOperator{\deg}{deg}$Luís Fernando Schultz Xavier da Silveira has answered the preceding problem in the affirmative, by doing a more careful analysis (similar to Bareiss’) of the specific linear system that arises from Tutte’s embedding algorithm. (In there, he uses planarity, in particular that $\sum_{v\in V(G)}\deg^2(v) \in O(n)$.)

The difficulty in this problem comes from graphs that are internally 3-connected, but not 3-connected: It is known that, if the triconnected component decomposition tree of $G$ has at $\ell\le 4$ leaves, then $G$ has a convex drawing on an $O(n)\times O(n)$ grid. See Chrobak (for the three connected case), Kamada, Miura, and Nishizeki (for $\ell\in\{1,2,3\}$), and Zhou and Nishizeki (for $\ell = 4$). The problem seems to be completely open for $\ell \ge 5$. It’s not even known if this can be done on a polynomial grid.

Fixing y-coordinates

An extension of Tutte’s Theorem implies that, not only can the outer face of $G$ be specified, but one can also fix the $y$-coordinates of $G$’s vertices provided that every vertex has at least one neighbour above it and at least one neighbor below it. This follows from an extension of Tutte’s proof to the case where every vertex is assigned a weighted average of its neighbours. See Floater or Gortler, Gotsmand, and Thurston. This result also seems to appear in a paper by Hong and Nagamochi.

The same argument of Bareiss’ algorithm implies that the resulting drawing can be achieved with integer $x$-coordinates no larger than $n^{O(n^2)}$. A lower bound construction, due to Lin and Eades, shows that $x$-coordinates of size $n^{\Omega(n)}$ may be necessary. A resolution to the second problem above would get matching upper and lower bounds.