Drawing Trees and Cacti with Integer Edge Lengths on a Polynomial-Size Grid

Wagner in 1936 [17], Fáry in 1948 [7], and Stein in 1951 [14] proved independently that every planar graph has a crossings-free drawing with edges drawn by straight-line segments. After these first existential results, algorithms that do create such drawings were described by Tutte in 1963 [16], Chiba, Yamanouchi, and Nishizeki in 1984 [5], and Read in 1986 [12]. In the generated drawings, the ratio between longest and shortest edge can be exponential in the size of the graph. For readability, it helps to have vertices at integer coordinates on a polynomial-size grid. In 1990, two algorithms generating such drawings appeared. De Fraysseix, Pach and Polack [6] use canonical orders whereas Schnyder’s algorithm [13] uses a decomposition of the graph into three trees from which barycentric coordinates can be computed. For $n$ vertices, both algorithms provide a straight-line drawing on the $𝒪(n)\times 𝒪(n)$ grid.

Can we also ensure that all edge lengths are integers? These two algorithms [6, 13] can (and do) produce irrational edge lengths. Harborth’s conjecture [9, 10] asks whether every planar graph has a crossings-free realization with straight-line segments of integer lengths, referred to integral Fáry embeddings [4]. A stronger version of Harborth’s conjecture, called Kleber’s conjecture, asks whether an integral Fáry embedding exists with all vertices on the integer grid [11]. We refer to these drawings as truly integral Fáry embeddings.

Sun [15] uses rigidity matrices to prove that all planar (2, 3)-sparse graphs admit integral Fáry embeddings. A graph $G$ is ($a$, $b$)-sparse if every subgraph $G^{\prime }$ of $G$ has at most $a|V(G^{\prime })|-b$ edges. (2, 3)-sparse graphs include series-parallel, outerplanar, and planar bipartite graphs. In 2024, Chang and Sun [4] show this result also for all planar 4-regular graphs.

Geelen, Guo, and McKinnon [8] show that every planar max-degree-3 graph admits a truly integral Fáry embedding. Biedl [3] observes that this technique can be applied to all planar (2, 1)-sparse graphs, which include all max-degree-4 graphs that are non-4-regular. Independently, Benediktovich [1] shows this result for max-degree-4 graphs that are non-4-regular and for planar 3-trees. The vertices have rational coordinates, thus, can be scaled to integers. However, they make use of a theorem by Berry [2] to position vertices on a rational point in an $\epsilon$-disk around a real point, which doesn’t provide guarantees on the distance towards an integral point. If the drawing is scaled to provide a truly integral Fáry embedding, no bound on the area can be provided. To the best of our knowledge, the algorithm by Biedl [3] that produces quadratic truly integral Fáry embeddings for $3$-regular planar graphs is the only algorithm in the literature that provides a polynomial upper bound on the area.

We show that trees and cacti admit truly integral Fáry embeddings on the $𝒪(n^2)\times 𝒪(n^2)$ and $𝒪(n^3)\times 𝒪(n^3)$ integer grids, respectively. For binary trees, $𝒪(n^2)$ follows from [3]; for constant-depth trees like stars, $𝒪(n^2)$ follows from Theorem 1. To ensure integer edge lengths on an integer grid, we are restricted to using Pythagorean triples. Pythagorean triples are all triples of integers $a,b,c$ which satisfy $a^2+b^2=c^2$. A Pythagorean triple is primitive if $a$, $b$, and $c$ are co-prime. The first $k$ primitive Pythagorean triples ${𝒫}_k$ can be computed in $𝒪(k^{3/2})$ time. We denote by ${𝒫}_k^{\circ }$ the angle-sorted first $k$ primitive Pythagorean triples.

Let $T=(V,E)$ be a (rooted) tree, which has $n$ vertices, $\mathrm{\ell }$ leaves, and depth $d$. Denote the root by $r$; if no root is given, pick $r$ arbitrarily. If no rotation system is given, choose it arbitrarily. For a vertex $v\in V$, we denote by $T_v$ the subtree of $T$ rooted at vertex $v$ and by $L(T_v)$ the number of leaves in $T_v$. Place $r$ at $(0,0)$. Assign the first child $v_1$ of $r$ the first $L(T_{v_1})$ primitive Pythagorean triples from ${𝒫}_{\mathrm{\ell }}^{\circ }$, assign the second child $v_2$ of $r$ the next $L(T_{v_2})$ primitive Pythagorean triples from ${𝒫}_{\mathrm{\ell }}^{\circ }$, etc. Draw each child $v$ of $r$ at the coordinates $(x,y)$ where $(x,y,z)$ is the first primitive Pythagorean triple assigned to $v$. For each child $v$ of $r$, for which $v$ is not a leaf of $T$, we draw the subtree $T_v$ recursively: in the recursive call, we assume that the coordinate system is centered at the position of $v$ and we use exactly the primitive Pythagorean triples assigned to $v$; see Figure 1.

Correctness follows from the fact that we use distinct slopes (primitive Pythagorean triples) in distinct subtrees that are sorted such that they fan out. The realization as a linear-time algorithm is straight-forward, however, we add $𝒪({\mathrm{\ell }}^{3/2})$ additional running time for computing primitive Pythagorean triples, which needs to be done only once.

With a special handling of cycles, in particular triangles, we can extend the algorithm from trees to cacti and obtain the following result.