ICPC Asia Pacific Championship 2025 — Solution B. Three-Dimensional Embedding

B  Three-Dimensional Embedding

In this problem, we are asked to embed a given graph into the cubic space \([0, 400]^3\). This is not straightforward, so let us first consider how to embed it in a differently sized box (not necessarily a cube).

Suppose that one vertex is placed at \((0, 2, 0)\). With a suitable construction, we can attach five polylines to that vertex so that their endpoints lie at \((0, j, 0)\) for \(j = 0, 1, \ldots, 4\). We call this arrangement a gadget. We can center such a gadget at any position, not necessarily at \((0, 2, 0)\).

Step 1: \(3n \times 6 \times m\)

One possible embedding is to line up \(n\) gadgets horizontally and then make connections between these gadgets in each \(z\)-layer (a plane parallel to the \(xy\)-plane).

Place the \(i\)-th gadget so that its center is at \((1 + 3i, 2, 0)\) for \(i = 0, 1, \ldots, n - 1\). For each edge connecting vertices \(v\) and \(w\) in the original graph, choose one endpoint from the \(v\)-th gadget and one endpoint from the \(w\)-th gadget, and connect them as follows:

By assigning distinct \(z\)-layers to different edges, we avoid intersections. This produces an embedding in a box of size \(3n \times 6 \times m\).

Step 2: \(3n \times n/2 \times 19\)

We next aim to fit the graph into a more compact (and closer to cubic) space by reducing the number of \(z\)-layers used.

Let \(M\) be a matching in the graph, meaning that each vertex is incident to at most one edge in \(M\). We will use two consecutive \(z\)-layers to embed as many edges as possible. Suppose \(z_0\) and \(z_0 + 1\) are two consecutive layers. For the \(j\)-th edge \((v, w)\) in \(M\), do the following:

Polylines produced in this way do not intersect. With a greedy edge-coloring of the graph, we obtain \(9\) matchings, each embedded by the above method. Thus, we get an embedding in a box of size \(3n \times n/2 \times 19\).

Step 3: \(9\sqrt{n} \times 3\sqrt{n} \times 7\sqrt{n}\)

Finally, we arrange the gadgets in a rectangular grid to further balance the dimensions.

Let \(d\) be an integer to be chosen later. Label each gadget as \((i, j)\) for \(0 \le i \lt n/d\) and \(0 \le j \lt d\). Place gadget \((i, j)\) so that its center is at \((1 + 3i, 2 + 5j, 0)\). This arrangement ensures that none of the gadgets overlap.

We then form a matching in a contracted graph: for each \(i\), we contract the vertices corresponding to the gadgets \((i, 0), (i, 1), \ldots, (i, d - 1)\). The contracted graph has \(n/d\) vertices, each of degree at most \(5d\). Using a greedy edge-coloring again, we obtain \(10d - 1\) matchings. Each pair of gadgets in different columns \((i, \cdot)\) and \((i', \cdot)\) is connected by the method from Step 2.

For gadgets in the same column, say \((i, j)\) and \((i, j')\), we connect them in a single \(z\)-layer \(z = z_0\) as follows:

These polylines do not interfere with those connecting gadgets across different columns.

To decide \(d\), note the required space:

Setting \(d = \sqrt{n}/3\) yields a final embedding in a box of size \(9\sqrt{n} \times 3\sqrt{n} \times 7\sqrt{n}\), which fits within \([0, 400]^3\) for \(n \le 1600\) because \(9\sqrt{1600} = 360 \lt 400.\)

Overall, the time complexity of this construction is \(O\big(n\sqrt{n}\big)\).