# Visibility kernels of embedded graphs

Let $G$ be a connected graph embedded in the plane with all edges straight segments. For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with all turns at vertices within $[-\alpha,\alpha]$. That is, if you walked along the path, you would twist no more than $\pm \alpha$ at each vertex of the path. Define an $\alpha$-kernel as a set of vertices of $G$ from which every other vertex of $G$ is reachable by an $\alpha$-path. In a sense, $G$ can be "seen" from the kernel, with "lines of sight" crooked $\alpha$-paths. Finally, define $\mbox{ker}(\overline{G},\alpha)$ as the cardinality of the smallest $\alpha$-kernel for a particular embedding $\overline{G}$ of $G$. I'll give some examples before asking a question.

• For $G=K_n$ the complete graph on $n$ vertices, $\mbox{ker}(\overline{K_n},\alpha)=1$.

• For $G=P_n$ the path on $n$ vertices, for any $\alpha < \pi$, there is a "squashed" zigzag embedding $\overline{P_n}$ with $\mbox{ker}(\overline{P_n},\alpha)=\lfloor n/2 \rfloor$.

• For $G=K_{n,n}$ the complete bipartite graph, for any $\alpha < \pi$, there is an embedding $\overline{K_{n,n}}$ with $\mbox{ker}(\overline{K_{n,n}},\alpha)=2$. My question is, roughly, are there small-diameter $G$ with embeddings that force large $\alpha$-kernels? Note above that the diameters of $K_n$ and $K_{n,n}$ are $1$ and $2$ respectively, and the diameter of $P_n$ is $n-1$. Here is an attempt to phrase the question more formally:

Is there a class of graphs $G_n$ on $n$ vertices, each of diameter $\le d$, such that, for any $\alpha < \pi$, there are embeddings $\overline{G_n}$ with $\mbox{ker}(\overline{G_n},\alpha)$ growing monotonically with $n$?

Here $d$ is a constant independent of $n$. Again, informally: Can a large kernel be forced without concomitant increase in diameter?

Consider the $n$-dimensional affine space over a finite field with $q$ elements ($n\geq 2$ for connectivity reasons). Let $P$ be the set of points in it, $L$ be the set of lines, and $G_n$ be the bipartite graph of incidence of $P$ and $L$. Then any two points are connected with a path of length 2, so the diameter of the graph is 4, and it has $q^n+\frac{q^{n-1}(q^n-1)}{q-1}$ vertices.
On the other hand, if you embed this graph in a way you did with the complete bipartite graph, then $\mathop{ker}$ will be the smallest size of the dominating set $D$ which should have at least $\frac{q^n-1}{q-1}$ elements (this estimate is not sharp). Indeed, if $D$ contains all the points then it contains even at least $q^n$ vertices. Otherwise, take any point $p$ which is not in $D$ and consider all the $\frac{q^n-1}{q-1}$ lines passing through it. Each of them should either be in $D$, or contain a point from $D$, and all these points should be distinct.