Grid Drawings and the Chromatic Number*

NEW

Problem: Reconstructed conjecture: For every finite simple planar graph $G$ with $n$ vertices, there is an injective straight-line drawing $\varphi:V(G)\to \mathbb Z^2$, contained in an $n^{O(1)}\times n^{O(1)}$ grid, such that edges do not cross and every edge segment is primitive:

$$\overline{\varphi(u)\varphi(v)}\cap \mathbb Z^2=\{\varphi(u),\varphi(v)\} \quad\text{for all }uv\in E(G).$$

This matches Balko’s definition: “A primitive planar grid drawing is proper.”

Result: The conjecture is true.

Sketch of proof. Take a standard polynomial-area straight-line plane grid drawing of $G$, e.g. by de Fraysseix–Pach–Pollack/Schnyder, and shear it by an integer affine map so all vertex $x$-coordinates are distinct while coordinates remain polynomially bounded. Let the drawing lie in $[0,B]^2$, $B=n^{O(1)}$. There is $\eta\ge B^{-O(1)}$ such that moving each vertex within its $\eta$-box preserves planarity: this follows because nonincident integer segments/vertices have separation at least $B^{-O(1)}$, and incident edge directions have angular separation at least $B^{-O(1)}$.

Four-color $G$, writing each color as $(a_v,b_v)\in\{0,1\}^2$. Since planar graphs are 5-degenerate, order vertices $v_1,\dots,v_n$ so each $v_i$ has at most five earlier neighbors.

Choose vertical grid lines inside each $\eta$-box so that

$$x(v)\equiv a_v \pmod 2,\qquad x(v)\equiv a_v \pmod 3.$$

This only needs constant refinement, so the width remains polynomial.

Now choose $y(v_i)$ sequentially. Always impose

$$y(v_i)\equiv b_{v_i}\pmod 2,\qquad y(v_i)\equiv b_{v_i}\pmod 3,\qquad y(v_i)\equiv \text{color}(v_i)\pmod 5.$$

For every earlier neighbor $v_j$ and every prime $p\ge7$ dividing $|x(v_i)-x(v_j)|$, additionally require

$$y(v_i)\not\equiv y(v_j)\pmod p.$$

At step $i$, at most five neighbors forbid residues modulo any such $p$, so since $p\ge7$, an allowed residue exists. By the Chinese remainder theorem, these congruences have a solution modulo

$$M_i\le 30\prod_{v_jv_i\in E,\ j<i}|x(v_i)-x(v_j)|\le n^{O(1)}.$$

Refine horizontal spacing so every $\eta$-box contains representatives of every residue modulo every $M_i$. Since $\max_i M_i=n^{O(1)}$, the height is still polynomial.

For an edge $v_jv_i$ with $j<i$, suppose a prime $p$ divides both coordinate differences. If $p=2$ or $3$, then divisibility of the $x$-difference forces $a_{v_i}=a_{v_j}$, hence $b_{v_i}\ne b_{v_j}$, so $p\nmid y(v_i)-y(v_j)$. If $p=5$, distinct colors give distinct residues mod $5$. If $p\ge7$, the sequential construction explicitly avoided equality mod $p$. Thus

$$\gcd(|x(v_i)-x(v_j)|,\ |y(v_i)-y(v_j)|)=1,$$

so the edge segment is primitive. Planarity is preserved because all chosen points remain inside the perturbation boxes. Hence $G$ has a proper grid drawing in polynomial size.

Citation: The conjecture and terminology are from M. Balko, “Grid Drawings and the Chromatic Number,” GD 2012, LNCS 7704, Springer, 2013, DOI: 10.1007/978-3-642-36763-2_28. Standard ingredients used: the Four Color Theorem, planar 5-degeneracy, the Chinese remainder theorem, and polynomial-area planar grid drawings of de Fraysseix–Pach–Pollack/Schnyder.