Does a Specific "Slicing" Partition for Any 2-Dimensional Integer Lattice Graph Always Exist?

Question

Inspired by this, I have been thinking about a question for some days:

Suppose $G=(V, E)$ is a graph that each vertex $u$ in $V$ corresponds to a different 2-dimensional integer point $(m, n)$. An edge $(u, v)$ is contained in $E$ if and only if $u, v$ are exactly $1$ unit apart from (adjacent to) each other.

Now define a partition $P=\{S_1, S_2,\ldots,S_m\}$ is a "sliced" partition of $G$ if and only if

For every $u, v$ that $u∈S_i, v∈S_j, (u, v)∈E$, we have $j∈[i - 1, i + 1]$.

This means a vertex in $S_i$ can only be adjacent to vertices in $S_{i-1}, S_i, $ or $S_{i+1}$.

Is the following statement true?

For any such graph $G$ with $N$ vertices, there always exists a "sliced" partition $P$ of $G$ that $S_i$ in $P$ with maximum number of vertices has no more than $O(\sqrt N)$ vertices.

I spent some time and proved that a "sliced" partition of $n * n$ lattice grid will have at least one slice with $n$ vertices.
I also found out partition by simply doing Breadth-first search wouldn't work, since there is a counter-example that exceeds $O(\sqrt N)$ vertices by constructing a tree-like graph of a large size.
What can I do now?

Answer 1

Up to a factor of $2$, trying to minimize the size of the largest slice is the same as ordering the vertices of a graph while trying to minimize the distance between adjacent vertices. In one direction, suppose we have a slicing partition $S_1,\dots, S_m$ with $|S_i|\le k$ for all $i$. Then ordering the vertices by slice (and then arbitrarily within a slice) means that two adjacent vertices are at most $\max_i \{|S_i| + |S_{i+1}|\} \le 2k$ apart. Conversely, suppose we have a vertex ordering $v_1,v_2,\dots,v_n$ such that whenever $v_iv_j$ is an edge, $|i-j|\le k$. Then dividing the ordering into blocks of size $k$ gives a slicing partition.

With this in mind, I can make partial progress and prove an upper bound of $O(N^{3/4})$ rather than the $O(N^{1/2})$ we want.

By the Szemerédi–Trotter theorem, whatever the vertices of the lattice graph are, there are $O(N^{1/2})$ lines (in the plane) which pass through more than $N^{1/2}$ vertices. We can pick an interval $I = [C N^{1/4}, 2C N^{1/4}) \cap \mathbb Z$, by picking the constant $C$, so that the number of pairs $(a,b) \in I \times I$ is more than the number of such lines.

Throw away every pair $(a,b) \in I \times I$ such that there is a line $ax + by = c$ passing through more than $N^{1/2}$ vertices of the graph. (Any such line can be represented by at most one pair $(a,b) \in I \times I$)

There is still at least one pair $(a^*, b^*)$ left. Now sort all the vertices $(m,n)$ of our graph by the value of $a^*m + b^*n$. Break ties arbitrarily.

Any two adjacent vertices are $\max\{a^*, b^*\} = O(N^{1/4})$ values apart, and for each value there are at most $N^{1/2}$ vertices with that value. (If the value is $c$, there are at most $N^{1/2}$ vertices on the line $a^*x + b^*y = c$.) So the indices of any two adjacent vertices differ by at most $O(N^{3/4})$ in this ordering, which gives a slicing partition where the maximum size of a slice is $O(N^{3/4})$, too.

Answer 2

With a similar approach as another answer provided by @MishaLavrov, which is to prove the existence of an angle that, when we slice the graph $G$ from its direction, gives a good upper bound $O((NlogN)^{1/2})$ for the number of vertices in the largest "slice".

For any vertex set $V$ and line $L$, let $C(V, L)$ denotes all the vertices in $V$ that are less than $1/2$ distance away from $L$.
For an angle $\alpha$, we can have parallel lines $L_1, L_2, L_3, \dots, L_m$ that are perpendicular to $\alpha$, and adjacent lines are $1$ unit apart from each other.
Note that this makes a partition $P_\alpha = \{C(V, L_1), C(V, L_2), C(V, L_3), \dots, C(V, L_m)\}$(we can avoid including the same vertex multiple times by exclude a border and include another) for any given angle $\alpha$. It is easy to see such partitions are "sliced".

Let $V_c$ be a copy of original vertex set $V$. Start from i = 1, repeat the following steps:

1.Let $L_i$ be the line with maximized number of vertices in $C(V_c, L_i)$ among all the lines in the plane, $\theta_i$ be the angle that perpendicular to $L_i$. If the number of vertices $\#C(V_c, L_i)$ is less than $(NlogN)^{1/2}$, end the loop, else go to step 2.
2.$V_c = V_c - C(V_c, L_i)$, $i = i + 1$. Repeat the first step.

Let $b$ be the number of times the loop goes back to the first step, it is clear that $b \le (N/logN)^{1/2}$ because every time the loop repeats at least $(NlogN)^{1/2}$ vertices are taken from $V_c$.
Note that if we "slice" the vertices left in $V_c$ from any angle $\alpha$ , the largest slice will have no more than $(NlogN)^{1/2}$ vertices.

Each of the rest of the vertices lies beside at least one of the lines $L_1, L_2, L_3, \dots, L_b$. We can see that for any $i\in [1, b], j\in[1, m]$, $P_\alpha$ be a "sliced" partition of $V$ made by $\alpha$ with $m$ slices, and let $\beta$ equals the angle between $\alpha$ and $\theta_i$(the angle perpendicular to $L_i$), then $$\frac{c_0}{sin(\beta)} + c_1$$ is an upper bound of $\#C(S_j, L_i)$ for $S_j$ in $P_a$, constants $c_0, c_1$ that are big enough. This is because $\#C(S_j, L_i)$ is the number of vertices that are close to both lines(in a diamond shape).

Let $Q$ be all the angles $\alpha \in [0, 2\pi)$ and for every $i\in [1, b]$, the angle between $\theta_i$ and $\alpha$ is larger than $\frac{c_2}{N^{1/2}}$ for a constant $c_2$ that is small enough.

By controlling the value of $c_2$, $Q$ can have a size that is constant($\Omega(1)$) regardless of how large $N$ is.

Now we will pick the final angle $\alpha$ we will "slice" the graph $G$ with from $Q$, and give an upper bound to the vertices number $$(\sum_{i=1}^b \#C(S_j, L_i)) + O((NlogN)^{1/2})$$ for every slice $S_j$ regardless of what $j$ is.

Note that because

$$\int_{x=\frac{1}{a}}^1 (\frac{c_0}{sin(x)} + c_1) dx = O(log(a))$$ the left side$\sum_{i=1}^b \#C(S_j, L_i)$ will have an average value less than $b * O(log\frac{N^{1/2}}{c_2}) = O((NlogN)^{1/2})$ vertices when we are picking $a$ from the range of $Q$. So there is a single $a$ with less than average ($O((NlogN)^{1/2})$) vertices in the left side.

Such an $a$ will make the $P_a$ a "sliced" partition with its largest slice having no more than $O((NlogN)^{1/2})$ vertices.