#  $k$-Domination invariants on Kneser graphs

Boštjan Brešar  Faculty of Natural Sciences and Mathematics, University of
Maribor, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana,
Slovenia  María Gracia Cornet  Depto. de Matemática, FCEIA, Universidad
Nacional de Rosario, Argentina  Consejo Nacional de Investigaciones
Científicas y Técnicas, Argentina  Tanja Dravec  Faculty of Natural Sciences
and Mathematics, University of Maribor, Slovenia Institute of Mathematics,
Physics and Mechanics, Ljubljana, Slovenia  Michael A. Henning  Department of
Mathematics and Applied Mathematics, University of Johannesburg, South Africa

###### Abstract

In this follow-up to [M.G. Cornet, P. Torres, arXiv:2308.15603], where the
$k$-tuple domination number and the 2-packing number in Kneser graphs $K(n,r)$
were studied, we are concerned with two variations, the $k$-domination number,
$\gamma_{k}(K(n,r))$, and the $k$-tuple total domination number,
$\gamma_{t\times k}(K(n,r))$, of $K(n,r)$. For both invariants we prove
monotonicity results by showing that
$\gamma_{k}(K(n,r))\geq\gamma_{k}(K(n+1,r))$ holds for any $n\geq 2(k+r)$, and
$\gamma_{t\times k}(K(n,r))\geq\gamma_{t\times k}(K(n+1,r))$ holds for any
$n\geq 2r+1$. We prove that $\gamma_{k}(K(n,r))=\gamma_{t\times
k}(K(n,r))=k+r$ when $n\geq r(k+r)$, and that in this case every
$\gamma_{k}$-set and $\gamma_{t\times k}$-set is a clique, while
$\gamma_{k}(r(k+r)-1,r)=\gamma_{t\times k}(r(k+r)-1,r)=k+r+1$, for any $k\geq
2$. Concerning the 2-packing number, $\rho_{2}(K(n,r))$, of $K(n,r)$, we prove
the exact values of $\rho_{2}(K(3r-3,r))$ when $r\geq 10$, and give sufficient
conditions for $\rho_{2}(K(n,r))$ to be equal to some small values by imposing
bounds on $r$ with respect to $n$. We also prove a version of monotonicity for
the $2$-packing number of Kneser graphs.

Keywords: Kneser graphs, $k$-domination, $k$-tuple total domination,
$2$-packing.

AMS subject classification (2010): 05C69, 05D05

##  1 Introduction

Letting $n\geq 2r$ the Kneser graph $K({n,r})$ has the $r$-subsets of an
$n$-set as its vertices and two vertices are adjacent in $K({n,r})$ if the
corresponding sets are disjoint. The interest for Kneser graphs goes back to
1960s and 1970s when two classical theorems concerning their independence and
chromatic number were proved [5, 18]. Many other graph invariants have been
investigated in Kneser graphs, which makes them one of the most intensively
studied classes of graphs. In particular, several authors have considered the
domination number of Kneser graphs (see the most recent paper [19]), but only
lower and upper bounds have been found in general, while the exact values of
$\gamma(K({n,r}))$ were found only when $n$ is sufficiently large with respect
to $r$. In three recent papers, the authors have considered Kneser graphs in
relation with some variations of domination, namely, Grundy domination [2],
Roman domination [21] and $k$-tuple domination [4]. This paper is a follow-up
of the latter, where we extend our investigation from $k$-tuple domination to
two similar variations, which we next present.

A _dominating set_ in a graph $G$ is a set $S$ of vertices of $G$ such that
every vertex outside $S$ is adjacent to at least one vertex in $S$. The
_domination number_ of $G$, denoted by $\gamma(G)$, is the minimum cardinality
of a dominating set in $G$. A thorough treatise on dominating sets can be
found in the so-called “domination books” [11, 12, 13, 16].

Let $G$ be a graph and $k\in\mathbb{N}$. A set $D\subseteq V(G)$ is a
$k$-dominating set of $G$ if every vertex $u\in V(G)\setminus D$ has at least
$k$ neighbors in $D$ (or, equivalently, if $|N_{G}(u)\cap D|\geq k$ for each
$u\in V(G)\setminus D$ where $N_{G}(u)$ denotes the open neighborhood of the
vertex $u$ in $G$). The $k$-domination number of $G$ is the minimum
cardinality of a $k$-dominating set of $G$, and is denoted by $\gamma_{k}(G)$.
A $\gamma_{k}$-set of $G$ is a $k$-dominating set of cardinality
$\gamma_{k}(G)$. See [6, 7, 3, 9] for a selection of papers considering
$k$-domination.

A set $D\subseteq V(G)$ is a $k$-tuple dominating set of $G$ if the closed
neighborhood $N_{G}[u]$ of each vertex $u\in V(G)$ has at least $k$ vertices
in $D$ (or, equivalently, if $|N_{G}[u]\cap D|\geq k$ for each $u\in V(G)$).
The $k$-tuple domination number of $G$ is the minimum cardinality of a
$k$-tuple dominating set of $G$, and is denoted by $\gamma_{\times k}(G)$. A
$\gamma_{\times k}$-set of $G$ is a $k$-tuple dominating set of cardinality
$\gamma_{\times k}(G)$. See [10, 9] for a selection of papers on $k$-tuple
domination.

Finally, a set $D\subseteq V(G)$ is a $k$-tuple total dominating set of $G$ if
the open neighborhood of each vertex $u\in V(G)$ has at least $k$ vertices in
$D$ (that is, if $|N_{G}(u)\cap D|\geq k$ for each $u\in V(G)$). The $k$-tuple
total domination number of $G$ is the minimum cardinality of a $k$-tuple total
dominating set of $G$, and is denoted by $\gamma_{t\times k}(G)$. As usual, a
$\gamma_{t\times k}$-set of $G$ stands for a $k$-tuple total dominating set of
$G$ of cardinality $\gamma_{t\times k}(G)$. The $k$-tuple total domination
number was studied, for example, in [14, 15], while all three invariants were
studied for the case $k=2$ in [1].

Note that $\gamma_{\times k}(G)$ is defined only in graphs $G$ with
$\delta(G)\geq k-1$, while $\gamma_{t\times k}(G)$ is defined only if
$\delta(G)\geq k$, where $\delta(G)$ denotes the minimum degree of vertices in
$G$. One can derive immediately from the definitions that

$\gamma_{k}(G)\leq\gamma_{\times k}(G)\leq\gamma_{t\times k}(G)$ (1)

holds for any graph $G$ in which the corresponding invariants are defined.
Clearly, when $k=1$, both $\gamma_{\times 1}(G)$ and $\gamma_{1}(G)$
correspond to the well-known domination number $\gamma(G)$, and
$\gamma_{t\times 1}(G)$ corresponds to the total domination number
$\gamma_{t}(G)$. In this paper, we denote by $\gamma_{k}(n,r)$,
$\gamma_{\times k}(n,r)$ and $\gamma_{t\times k}(n,r)$ the $k$-domination
number, the $k$-tuple domination number and the $k$-tuple total domination
number, respectively, of the Kneser graph $K({n,r})$.

Concerning the domination number of Kneser graphs, it was shown to be
monotonically decreasing when $r$ is fixed and $n$ grows [8] and a similar
result was proved for the $k$-tuple domination number in [4]. In this vein we
prove in Section 2 that $\gamma_{t\times k}(n,r)\geq\gamma_{t\times k}(n+1,r)$
and $\gamma_{k}(n,r)\geq\gamma_{k}(n+1,r)$ hold for any positive integers $n$
and $r$, where $n\geq 2r+1$, respectively $n\geq 2(k+r)$. In Section 3, we
obtain exact values for these two invariants in $K(n,r)$ when $n$ is
sufficiently large with respect to $r$. Notably, we prove that
$\gamma_{k}(n,r)=\gamma_{t\times k}(n,r)=k+r$ as soon as $n\geq r(k+r)$, and,
in addition, every $\gamma_{k}$-set and $\gamma_{t\times k}$-set is a clique
in this case. When $n$ is one less, we also get exact values, namely, if
$k\geq 2$, we have $\gamma_{k}(r(k+r)-1,r)=\gamma_{t\times
k}(r(k+r)-1,r)=k+r+1$. In Section 4, we study the 2-packing number,
$\rho_{2}(K(n,r))$, of Kneser graphs, which is the largest cardinality of a
set of vertices in the graph, which are pairwise at distance at least $3$
apart. We continue the study from [4], where the $2$-packing number was used
for bounding the $k$-tuple domination number of $K(n,r)$, and
$\rho_{2}(K(3r-2,r))$ was also determined for all values of $r$. Here we go a
step further by considering $\rho_{2}(K(3r-3,r))$, where we obtain lower
bounds when $r\leq 8$, prove that $4$ is the exact value for $r=9$, and that
$3$ is the exact value when $r\geq 10$. We also give sufficient conditions for
$\rho_{2}(K(n,r))$ being equal to $3$, resp. $4$, by imposing bounds on $r$
with respect to $n$. In addition, we prove a version of monotonicity, by
showing that $\rho_{2}(K(n+1,r+1))\geq\rho_{2}(K(n,r))$ as soon as $n\geq
2r+2$.

We conclude the introduction with several useful definitions. For
$r,n\in\mathbb{N}$ with $r\leq n$, let $[r..n]$ and $[n]$ denote the sets
$\\{r,\ldots,n\\}$ and $\\{1,\ldots,n\\}$ respectively. Given a set of
vertices $D$ in $K({n,r})$ and $x\in[n]$, the occurrences of the element $x$
in $D$, denoted by $i_{x}(D)$, represent the number of vertices in $D$ that
contain the element $x$. This is, $i_{x}(D)=|\\{u\in D:x\in u\\}|$. For a
positive integer $a$, we define $X_{a}(D)$ as the set of elements in $[n]$
such that their occurrences in $D$ is equal to $a$, i.e.,
$X_{a}(D)=\\{x\in[n]:i_{x}(D)=a\\}$. Similarly, we define
$X_{a}^{\geq}(D)=\\{x\in[n]:i_{x}(D)\geq a\\}$, and
$X_{a}^{\leq}(D)=\\{x\in[n]:i_{x}(D)\leq a\\}$. When the set $D$ is clear from
the context, we shall omit it in the notation. It is important to note that
the sum of the occurrences of all elements in $D$ is equal to $r$ times the
cardinality of $D$, i.e., $\sum_{x\in[n]}i_{x}(D)=r|D|$.

##  2 Monotonicity

In [4] it is proved that the function $\gamma_{\times k}(n,r)$ is decreasing
with respect to $n$. Using the same idea, we prove the analogous statement for
the function $\gamma_{t\times k}(n,r)$. Regarding the $k$-domination number,
we show that $\gamma_{k}(n,r)$ is decreasing with respect to $n$ from
$n_{0}=2(k+r)$.

Note that, using the standard notation for vertices of Kneser graphs, a vertex
$u\in V(K(n,r))$ also belongs to $K(n+1,r)$, since it is represented as an
$r$-subset of $[n]\subset[n+1]$. When $r$ is fixed, we will simplify the
notation by writing $N_{n}(u)$ for the neighborhood $N_{K(n,r)}(u)$, where
$u\subset[n]$ with $|u|=r$. In this sense, the meaning of $N_{n+1}(u)$ should
also be clear.

######  Theorem 1.

For any positive integers $n$ and $r$, where $n\geq 2r+1$,

$\gamma_{t\times k}(n,r)\geq\gamma_{t\times k}(n+1,r).$

That is, $\gamma_{t\times k}(n,r)$ is decreasing with respect to $n$.

###### Proof.

Let $D$ be a $\gamma_{t\times k}$-set of $K({n,r})$. Let us show that $D$ is a
$k$-tuple total dominating set of $K({n+1,r})$. Let $u\in V(K({n+1,r})$. If
$u\in V(K({n+1,r}))\cap V(K({n,r}))$, then $|N_{n+1}(u)\cap D|=|N_{n}(u)\cap
D|\geq k$. If $u\in V(K({n+1,r}))\setminus V(K({n,r}))$, then we have
$u=\tilde{u}\cup\\{n+1\\}$ with $\tilde{u}\subseteq[n]$, $|\tilde{u}|=r-1$.
Let $x\in[n]\setminus\tilde{u}$, and let $w=\tilde{u}\cup\\{x\\}$. Since $w\in
V(K({n+1,r}))\cap V(K({n,r}))$, then $|N_{n+1}(w)\cap D|\geq k$. On the other
hand,

$N_{n+1}(w)\cap D=\\{v\in D:v\cap w=\emptyset\\}\subseteq\\{v\in
D:v\cap\tilde{u}=\emptyset\\}=\\{v\in D:v\cap u=\emptyset\\}.$

Thus, we have $|N_{n+1}(u)\cap D|\geq|N_{n+1}(w)\cap D|\geq k$. Therefore, $D$
is a $k$-tuple total dominating set of $K({n+1,r})$. Consequently,
$\gamma_{t\times k}(n+1,r)\leq|D|=\gamma_{t\times k}(n,r)$. ∎

######  Lemma 2.

If $n\geq 2(k+r)$, $D$ is a $\gamma_{k}$-set of $K({n,r})$ and
$\tilde{u}=\\{a_{1},\ldots,a_{r-1}\\}\subseteq[n]$, then there exists
$x\in[n]\setminus\tilde{u}$ such that $\tilde{u}\cup\\{x\\}\notin D$.

###### Proof.

Suppose that $\tilde{u}\cup\\{x\\}\in D$ for each
$x\in[n]\setminus\tilde{u}=\\{x_{1},x_{2},\ldots,x_{n-r+1}\\}$, and let
$u_{i}=\tilde{u}\cup\\{x_{i}\\}$ for each $i\in[n-r+1]$. Let
$D^{\prime}=(D\setminus\\{u_{1},\ldots,u_{k+1}\\})\cup\\{v_{1},\ldots,v_{k}\\}$,
where $v_{i}=\\{x_{k+2},\ldots,x_{k+r},x_{k+r+i}\\}$ for $i\in[k]$. It is
possible since $n\geq 2(k+r)$.

Let us see that $D^{\prime}$ is a $k$-dominating set of $K({n,r})$. Let $w\in
V(K({n,r}))\setminus D^{\prime}$.

  * •

If $w\cap\tilde{u}=\emptyset$ (and $w\neq u_{i}$ for each $i\in[k+1]$), then
as $|w\cap\\{x_{k+2},\ldots,x_{n-r+1}\\}|\leq r$, we have $|N(w)\cap
D^{\prime}|\geq|\\{u_{i}:i\geq k+2\wedge x_{i}\notin w\\}|\geq|\\{u_{i}:i\geq
k+2\\}|-r=(n-r-k)-r\geq k$ since $n\geq 2(k+r)$.

  * •

If $w\cap\tilde{u}\neq\emptyset$ and $w\neq u_{i}$ for each $i\in[k+1]$, then
$|N(w)\cap D^{\prime}|\geq|N(w)\cap D|\geq k$, since the vertices eliminated
from $D$ were not neighbors of $w$.

  * •

If $w=u_{i}$ for some $i\in[k+1]$, then we have $|N(w)\cap
D^{\prime}|\geq|\\{v_{1},\ldots,v_{k}\\}|=k$.

Therefore, $D^{\prime}$ is a $k$-dominating set of $K({n,r})$ of size
$|D^{\prime}|=|D|-1=\gamma_{k}(n,r)-1$, and we arise to a contradiction. Thus,
there is at least one element $x\in[n]\setminus\tilde{u}$ such that
$\tilde{u}\cup\\{x\\}\notin D$. ∎

######  Theorem 3.

For any positive integers $n$ and $r$, where $n\geq 2(k+r)$,

$\gamma_{k}(n,r)\geq\gamma_{k}(n+1,r).$

###### Proof.

Let $n\geq 2(k+r)$ and let $D$ be a $\gamma_{k}$-set of $K({n,r})$. Let us
show that $D$ is a $k$-dominating set of $K({n+1,r})$. Let $u\in
V(K({n+1,r}))\setminus D$. If $u\subseteq[n]$, then $|N_{n+1}(u)\cap
D|=|N_{n}(u)\cap D|\geq k$. Otherwise, $u\in V(K({n+1,r}))\setminus
V(K({n,r}))$. It follows that $u=\tilde{u}\cup\\{n+1\\}$ with
$\tilde{u}=\\{a_{1},\ldots,a_{r-1}\\}\subseteq[n]$. By Lemma 2 there exists
$x\in[n]\setminus\tilde{u}$ such that $w=\tilde{u}\cup\\{x\\}\notin D$. Thus,
we have

$\displaystyle N_{n}(w)\cap D$ $\displaystyle=N_{n+1}(w)\cap D=\\{v\in D:v\cap
w=\emptyset\\}=$ $\displaystyle=\\{v\in D:v\cap\tilde{u}=\emptyset\wedge
x\notin v\\}\subseteq\\{v\in D:v\cap\tilde{u}=\emptyset\\}=N_{n+1}(u)\cap D.$

Consequently,

$|N_{n+1}(u)\cap D|\geq|N_{n}(w)\cap D|\geq k.$

Therefore, $D$ is a $k$-dominating set of $K({n+1,r})$ and we have

$\gamma_{k}(n+1,r)\leq|D|=\gamma_{k}(n,r).$

∎

Note that $\gamma_{k}(n,r)$ is not necessarily decreasing for any $n$, but
$\gamma_{k}(n_{1},r)\geq\gamma_{n}(n_{2},r)$ holds for any $n_{1}\leq n_{2}$,
if $n_{1}$ is large enough. To see that the monotonicity may not hold if
$n_{1}$ is small, consider the Kneser graphs $K(n,2)$, where
$\gamma_{2}(5,2)<\gamma_{2}(6,2)$, $\gamma_{2}(6,2)=\gamma_{2}(7,2)$ and
$\gamma_{2}(7,2)>\gamma_{2}(8,2)$, see Table 1.

##  3 Exact values for large $n$

In [4], the following result is stated.

######  Theorem 4 ([4]).

For any $n\geq 2r$, $\gamma_{\times k}(n,r)=k+r$ if and only if $n\geq
r(k+r)$.

Moreover, it is shown that except in the case $k=1$ and $r=2$, every
$\gamma_{\times k}$-set of $K(n,r)$, where $n\geq r(k+r)$, is a clique. If
$k=1$ and $r=2$, then in [17] it is proved that a $\gamma_{\times 1}$-set of
$K(n,2)$ is either a clique or an independent set. In any case, if
$\gamma_{\times k}(n,r)=k+r$, then it is possible to obtain a $\gamma_{k}$-set
that is a clique. As a by-product, we get the following for the $k$-tuple
total domination number.

######  Theorem 5.

For any $n\geq 2r$, $\gamma_{t\times k}(n,r)=k+r$ if and only if $n\geq
r(k+r)$. Moreover, for any $n\geq r(k+r)$, every $\gamma_{t\times k}$-set is a
clique.

###### Proof.

Let $n,r,k\in\mathbb{N}$. If $n\geq r(k+r)$, then $\gamma_{t\times
k}(n,r)\geq\gamma_{\times k}(n,r)=k+r$. Since there exists a $\gamma_{\times
k}$-set $D$ which is a clique on $k+r$ vertices, it is also a $k$-tuple total
dominating set of $K({n,r})$. Thus, $\gamma_{t\times k}(n,r)=k+r$. Conversely,
if $\gamma_{t\times k}(n,r)=k+r$, then since any $\gamma_{t\times k}$-set $D$
is a $k$-tuple dominating set, then $\gamma_{\times k}(n,r)\leq|D|=k+r$. Due
to monotonicity of $\gamma_{\times k}(n,r)$ with respect to $n$, we have
$\gamma_{\times k}(n,r)=k+r$, and by Theorem 4 it follows that $n\geq r(k+r)$.
Hence $D$ is a $\gamma_{\times k}$-set of $K(n,r)$ for $n\geq r(k+r)$ and thus
$D$ is a clique by the results described before the theorem. ∎

######  Remark 6.

If $D$ is a $k$-dominating set of the Kneser graph $K({n,r})$ and $w\in
V(K({n,r}))\setminus D$, then $w$ has nonempty intersection with at most
$|D|-k$ vertices of $D$. Otherwise, $|N(w)\cap D|<k$ contradicting the fact
that $D$ is $k$-dominating.

######  Theorem 7.

If $k\geq 2$ and $n\geq k+2r$, then

  * •

$\gamma_{k}(n,r)=k+r$ if and only if $n\geq r(k+r)$; moreover, every
$\gamma_{k}$-set is a clique;

  * •

$\gamma_{k}(n,r)\geq k+r+1$ if and only if $n<r(k+r)$.

###### Proof.

Let $n,r,k\in\mathbb{N}$ such that $n\geq k+2r$. We start the proof by showing
that

$\gamma_{k}(n,r)\leq k+r\Rightarrow n\geq r\cdot(k+r).$ (2)

Thus, suppose that $\gamma_{k}(n,r)\leq k+r$ and let $D$ be an arbitrary
$k$-dominating set of $K({n,r})$ of cardinality $|D|=k+r$ (note that such a
set exists, since $n\geq k+2r$, and thus we can obtain $D$ by adding
$k+r-\gamma_{k}(n,r)$ vertices to a $\gamma_{k}(n,k)$-set). We will show that
$D$ is a clique or, equivalently, that the vertices in $D$ are pairwise
disjoint. Assume $D$ contains two adjacent vertices $u$ and $v$. Hence there
exists $j\in[n]$ such that $j\in u\cap v$ and consequently $i_{j}(D)\geq 2$.
Let $a\in[n]$ such that $i_{a}=\max\\{i_{x}:x\in[n]\\}$. Thus, $i_{a}\geq
i_{j}\geq 2$. Let us see that $i_{a}=2$. Otherwise, let $u_{1},u_{2},u_{3}\in
D$ such that $a\in u_{1}\cap u_{2}\cap u_{3}$, and $u_{4},\ldots,u_{r+1}\in
D\setminus\\{u_{1},u_{2},u_{3}\\}$. Consider

$\displaystyle b_{1}$ $\displaystyle=a\in u_{1}\cap u_{2}\cap u_{3},$
$\displaystyle b_{i}$ $\displaystyle\in
u_{i+2}\setminus\\{b_{1},\ldots,b_{i-1}\\},\ \text{for }i\in[2..r-1],$

and let $b=\\{b_{1},\ldots,b_{r-1}\\}$. Observe that there is at least one
element $x\in[n]\setminus b$ such that $b\cup\\{x\\}\notin D$, since
$|[n]\setminus b|-|D|=(n-r+1)-(k+r)=n-(k+2r)+1\geq 1$. Let $w=b\cup\\{x\\}$.
We have $w\notin D$ and $w\cap u_{i}\neq\emptyset$ for every $i\in[r+1]$ which
cannot be true because of Remark 6. Thus, $i_{a}=2$. Let $u_{1}$ and $u_{2}$
be the two vertices of $D$ that contain the element $a$.

If $r>2$, let $u_{3},\ldots,u_{r+1}\in D\setminus\\{u_{1},u_{2}\\}$. Consider

$\displaystyle b_{1}$ $\displaystyle=a\in u_{1}\cap u_{2},$ $\displaystyle
b_{i}$ $\displaystyle\in u_{i+1}\setminus\\{b_{1},\ldots,b_{i-1}\\},\
\text{for }i\in[2..r],$

and let $w=\\{b_{1},\ldots,b_{r}\\}$. We have $w\cap u_{i}\neq\emptyset$ for
every $i\in[r+1]$. By Remark 6, it follows that $w\in D$ and as $a\in w$, then
$w$ is either $u_{1}$ or $u_{2}$. Without loss of generality, $w=u_{1}$. Note
that $b_{i}\in u_{1}\cap u_{i+1}$ for every $i$, and since
$i_{a}=\max\\{i_{x}:x\in[n]\\}=2$, $b_{i}\notin u_{j}$ for every $j$ different
from $1$ and $i+1$. Let us consider $x\in u_{3}\setminus u_{1}$, and let
$w^{\prime}=w\setminus\\{b_{2}\\}\cup\\{x\\}$. We have $x\in
w^{\prime}\setminus u_{1}$ and $b_{r}\in w^{\prime}\setminus u_{2}$. Thus,
$a\in w^{\prime}$ and $w^{\prime}\notin\\{u_{1},u_{2}\\}$ and therefore
$w^{\prime}\notin D$ but $w^{\prime}\cap u_{i}\neq\emptyset$ for every
$i\in[r+1]$, arising to a contradiction with Remark 6.

If $r=2$, we have $u_{1}=\\{a,b\\}$ and $u_{2}=\\{a,c\\}$ for some
$b,c\in[n]$. Since $|D|=k+r\geq 4$, then we can choose $u_{3}\in D$
$u_{3}\neq\\{b,c\\}$. Let $x\in u_{3}\setminus\\{b,c\\}$. Since $i_{a}=2$,
$w=\\{a,x\\}\notin D$ and $w\cap u_{i}\neq\emptyset$ for $i\in[3]$,
contradicting the fact that $D$ is $k$-dominating.

Therefore, if $\gamma_{k}(n,r)\leq k+r$ and $D$ is a $k$-dominating set of
$K({n,r})$ of cardinality $k+r$, then the vertices in $D$ are pairwise
disjoint and as a consequence, $n\geq r|D|=r(k+r)$. In particular, if
$\gamma_{k}(n,r)=k+r$, then $n\geq r(k+r)$.

Conversely, suppose that $n\geq r(k+r)$. We have
$\gamma_{k}(n,r)\leq\gamma_{\times k}(n,r)=k+r$. Suppose that
$\gamma_{k}(n,r)<k+r$ and let $D$ be a $k$-dominating set of cardinality
$|D|=k+r-1$. Let $u_{1},\ldots,u_{r}\in D$. Consider

$\displaystyle b_{1}$ $\displaystyle\in u_{1},$ $\displaystyle b_{i}$
$\displaystyle\in u_{i}\setminus\\{b_{1},\ldots,b_{i-1}\\},\ \text{for
}i\in[2..r],$

and let $w=\\{b_{1},\ldots,b_{r}\\}$. Let us note that $w\cap
u_{i}\neq\emptyset$ for every $i\in[r]$. So, by Remark 6 it follows that $w\in
D$. Let us note that we may assume that $w=u_{j}$ for some $j\in[r]$ by
changing our initial choice of the vertices $u_{i}$. Notice that there exists
$x\in[n]\setminus\left(\bigcup_{u\in D}u\right)$, since
$\left|[n]\setminus\left(\bigcup_{u\in D}u\right)\right|\geq
n-r|D|=n-r(k+r-1)\geq r$. Let $w^{\prime}=w\setminus\\{b_{j}\\}\cup\\{x\\}$.
We have $w^{\prime}\notin D$ due to our choice of $x$, and $w^{\prime}\cap
u_{i}\neq\emptyset$ for each $i\in[r]$ (note that $u_{j}\cap
w^{\prime}=\\{b_{1},\ldots,b_{r}\\}\setminus\\{b_{j}\\}$), arising to a
contradiction with Remark 6.

Therefore, if $n\geq r(k+r)$, then $\gamma_{k}(n,r)=k+r$.

Suppose now that $\gamma_{k}(n,r)\geq k+r+1$. Then the first statement of the
theorem implies that $n<r(k+r)$. For the converse assume that $n<r(k+r)$. It
follows from the first statement of this theorem, that $\gamma_{k}(n,k)\neq
k+r$. Suppose, to the contrary, that $\gamma_{k}(n,r)<k+r$. Then it follows
from Equation 2 that $n\geq r(r+k)$, a contradiction. ∎

######  Corollary 8.

If $k\geq 2$ and $n\geq r(k+r)$, then

$\gamma_{k}(n,r)=\gamma_{\times k}(n,r)=\gamma_{t\times k}(n,r)=k+r.$

Moreover, every $\gamma_{k}$-set, $\gamma_{\times k}$-set and $\gamma_{t\times
k}$-set of $K(n,r)$, where $n\geq r(k+r)$, is a clique.

######  Proposition 9.

If $k\geq 2$, then

$\gamma_{k}(r(k+r)-1,r)=\gamma_{\times k}(r(k+r)-1,r)=\gamma_{t\times
k}(r(k+r)-1,r)=k+r+1.$

###### Proof.

Let $k\geq 2$ and $n=r(k+r)-1$. Since $n>k+2r$, from Theorem 7 we have that
$k+r+1\leq\gamma_{k}(n,r)\leq\gamma_{\times k}(n,r)\leq\gamma_{t\times
k}(n,r)$. We will give a $k$-tuple total dominating set $D$ of cardinality
exactly $k+r+1$.

It is enough to consider the set $D=A\cup B$, where

$\displaystyle A$
$\displaystyle=\big{\\{}[r],[r-1]\cup\\{r+1\\},[r..2r-1]\big{\\}}$
$\displaystyle B$
$\displaystyle=\big{\\{}[2r..3r-1],[3r..4r-1],\ldots,[(k+r-1)r..(k+r)r-1]\big{\\}}.$

We have that $A$ is an independent set of $|A|=3$ vertices, $B$ is a clique of
$|B|=k+r-2$ vertices, and $a$ is adjacent to $b$ for each $a\in A$ and $b\in
B$. Let $u\in V(K({n,r}))$.

  * •

If $u\in A$, then $u$ is adjacent to every vertex in $B$, so $|N(u)\cap D|\geq
k+r-2\geq k$.

  * •

If $u\in B$, then $u$ is adjacent to every other vertex in $D$, so $|N(u)\cap
D|\geq k+r>k$.

  * •

If $u\notin D$ and $|u\cap[2r-1]|\geq 2$, then $|u\cap[2r..n]|\leq r-2$ and
$u$ has at least $|B|-(r-2)=k$ neighbors in $B$. So, $|N(u)\cap D|\geq k$.

  * •

If $u\notin D$ and $|u\cap[2r-1]|=1$, then $|u\cap[2r..n]|=r-1$ and $u$ has at
least $|B|-(r-1)=k-1$ neighbors in $B$. On the other hand, since there is no
element contained in every vertex of $A$, we have that $u$ has at least one
neighbor in $A$. So, $|N(u)\cap D|=|N(u)\cap A|+|N(u)\cap B|\geq k$.

  * •

Finally, if $u\notin D$ and $|u\cap[2r-1]|=0$, then $|u\cap[2r..n]|=r$ and $u$
has at least $|B|-r=k-2$ neighbors in $B$, and $u$ is adjacent to every vertex
in $A$. So, $|N(u)\cap D|=|N(u)\cap A|+|N(u)\cap B|\geq k+1\geq k$.

∎

Combining the results of this section with results from [4], we obtain the
table of values of the three types of $k$-domination invariants of $K(n,r)$ in
the case $k=2$ and $r=2$; see Table 1.

$n$ | $\gamma_{2}(n,2)$ | $\gamma_{\times 2}(n,2)$ | $\gamma_{t\times 2}(n,2)$
---|---|---|---
$4$ | $6$ | $6$ | $\lnot\exists$
$5$ | $4$ | $6$ | $8$
$6$ | $5$ | $6$ | $6$
$7$ | $5$ | $5$ | $5$
$\geq 8$ | $4$ | $4$ | $4$
Table 1: Domination invariants with $k=2$ for $K({n,2})$.

##  4 2-packing number

The $2$-packing number of Kneser graphs was considered in [4]. Note that ${\rm
diam}(K(n,r))=2$ as soon as $n\geq 3r-1$, and in such cases
$\rho_{2}(K(n,r))=1$; see [20]. In [4], the authors studied the case, which is
in a sense the closest to diameter $2$ Kneser graphs, and this is when
$n=3r-2$. They obtained the exact values of the $2$-packing number for all
these Kneser graphs. In this paper, we consider the next case, which is when
$n=3r-3$. We again simplify the notation by writing $\rho_{2}(n,r)$ instead of
$\rho_{2}(K(n,r))$.

We start by recalling a useful observation from [4], which follows from the
fact that a set $S$ is a $2$-packing of a graph $G$ if and only if no two
vertices of $S$ are adjacent nor have a common neighbor.

######  Observation 10.

Let $2r+1\leq n\leq 3r-2$. A set $S$ is a $2$-packing in $K(n,r)$ if and only
if for every pair $u,v\in S$ we have $1\leq|u\cap v|\leq(3r-1)-n$.

In the case of $K(3r-3,r)$, Observation 10 yields that $S$ is a $2$-packing in
$K(n,r)$ if and only if for every pair $u,v\in S$ we have

$1\leq|u\cap v|\leq 2.$

We obtain lower bounds for $\rho_{2}(3r-3,r)$ when $r\leq 9$, and exact values
for $\rho_{2}(3r-3,r)$ when $r>9$. See Table 2. The lower bounds in Table 2
follow from constructions of the corresponding $2$-packings, which we present
in Table 3.

$r$ | $\rho_{2}(3r-3,r)$
---|---
$4$ | $\geq 12$
$5$ | $\geq 12$
$6$ | $\geq 10$
$7$ | $\geq 6$
$8$ | $\geq 5$
$9$ | $=4$
$\geq 10$ | $=3$
Table 2: $2$-packing numbers of $K({3r-3,r})$.

Consider the Kneser graph $K(3r-3,r)$, where $r\geq 2$. Since a set $S$ of
three vertices $u,v,w\in V(K(3r-3,r))$ with $|u\cap v\cap w|=|u\cap v|=|u\cap
w|=|v\cap w|=2$ is a 2-packing (say
$u=[1..r],v=\\{1,2\\}\cup[r+1..2r-2],w=\\{1,2\\}\cup[2r-1..3r-4]$), we infer
$\rho_{2}(3r-3,r)\geq 3$. The next result proves the last line of Table 2.

######  Proposition 11.

If $r\geq 10$, then $\rho_{2}(3r-3,r)=3$.

###### Proof.

Let $P$ be a $2$-packing of $K(3r-3,r)$, where $r\geq 10$, and let
$\\{u_{1},u_{2},u_{3}\\}\subseteq P$. Since $|u_{i}\cap u_{j}|\leq 2$ for all
$\\{i,j\\}\subset[3]$, we infer that $|[3r-3]\setminus(u_{1}\cup u_{2}\cup
u_{3})|\leq 3$. Suppose that $|P|\geq 4$, and let $z\in P$ be distinct from
all $u_{i}$. Since $z\in P$, $|z\cap u_{1}|\leq 2$, $|z\cap u_{2}|\leq 2$,
$|z\cap u_{3}|\leq 2$, and $|z\cap\left([3r-3]\setminus(u_{1}\cup u_{2}\cup
u_{3})\right)|\leq 3$. We derive that $|z|\leq 2+2+2+3=9$, which is a
contradiction, since $r\geq 10$. Hence, $|P|=3$. ∎

$r$ |  $2$-packing of $K(3r-3,r)$
---|---
$4$ |  (1, 2, 3, 5), (1, 2, 6, 9), (1, 2, 7, 8), (1, 3, 4, 6), (1, 4, 5, 8), (1, 4, 7, 9),(2, 3, 4, 7),
|  (2, 4, 5, 6), (2, 4, 8, 9), (3, 5, 7, 9), (3, 6, 8, 9), (5, 6, 7, 8)
$5$ |  (1, 2, 3, 4, 8), (1, 2, 5, 10, 11), (1, 2, 6, 9, 12), (1, 3, 7, 9, 10), (1, 4, 5, 7, 12),
|  (1, 6, 7, 8, 11), (2, 3, 5, 6, 7), (2, 4, 7, 9, 11), (2, 7, 8, 10, 12), (3,
4, 6, 10, 11),
|  (3, 5, 9, 11, 12), (4, 5, 6, 8, 9)
$6$ |  (1, 2, 3, 4, 5, 11), (1, 2, 7, 8, 9, 14), (1, 3, 6, 9, 10, 15), (1, 5, 6, 12, 13, 14),
|  (2, 4, 6, 7, 13, 15), (2, 5, 8, 10, 12, 15), (3, 4, 8, 10, 13, 14), (3, 6,
7, 8, 11, 12),
|  (4, 9, 11, 12, 14, 15), (5, 7, 9, 10, 11, 13)
$7$ |  (1, 2, 3, 4, 6, 11, 14), (1, 3, 5, 8, 16, 17, 18), (2, 4, 5, 7, 12, 15, 17),
|  (2, 8, 9, 12, 13, 14, 16), (3, 7, 8, 9, 10, 11, 15), (4, 5, 6, 9, 10, 13,
18),
$8$ |  (1, 2, 3, 4, 5, 6, 9, 18), (1, 2, 7, 11, 12, 14, 20, 21), (3, 7, 8, 9, 13, 15, 16, 20),
|  (4, 5, 10, 12, 13, 15, 17, 21), (5, 6, 8, 10, 11, 14, 16, 19)
Table 3: $2$-packings in $K({3r-3,r})$, for $r\leq 8$.

We suspect that the lower bounds in Table 2 are in fact exact values of
$\rho_{2}(3r-3,r)$, and leave this as an open problem. The proof for the
penultimate line in Table 2, as well as an alternative proof of Proposition
11, are given afterwards in Theorem 17.

We continue with several general results concerning the behavior of the
$2$-packing number in Kneser graphs.

######  Proposition 12.

If $n$, $r$ and $a$ are positive integers such that $n=2r+1$ and $a\geq 2$,
then

$\rho_{2}(n+2a,r+a)\geq 2\rho_{2}(n,r).$

###### Proof.

Let $S$ be a $2$-packing of $K(n,r)$ with $|S|=\rho_{2}(n,r)$. Consider the
following set:

$T=\Big{\\{}v\cup[(n+1)..(n+a)],v\cup[(n+a+1)..(n+2a)]:\,v\in S\Big{\\}}.$

Clearly, $T\subset V(K(n+2a,r+a))$ and $|T|=2\rho_{2}(n,r)$. Note that
$n+2a=2r+1+2a=2(r+a)+1$. Thus, to prove that $T$ is a $2$-packing in
$K(n+2a,r+a)$, we need to prove, by Observation 10, that

$1\leq|u\cap v|\leq(3(r+a)-1)-(n+2a)=3r-1-n+a=r+a-2$

for any two vertices $u,v\in T$. Let $u,v\in T$, and let $\tilde{u}=u\cap[n]$,
$\tilde{v}=v\cap[n]$. If $\tilde{u}\neq\tilde{v}$, then as
$\tilde{u},\tilde{v}\in S$, by Observation 10, we have
$1\leq|\tilde{u}\cap\tilde{v}|\leq(3r-1)-n=r-2$, and since
$|\tilde{u}\cap\tilde{v}|\leq|u\cap v|\leq|\tilde{u}\cap\tilde{v}|+a$, we have
$1\leq|u\cap v|\leq r+a-2$. On the other hand, if $\tilde{u}=\tilde{v}$, then
$|u\cap v|=r$ and it follows $1\leq|u\cap v|=r\leq r+a-2$ since $a\geq 2$. ∎

By applying Proposition 12 several times (note that if $K(n,r)$ is an odd
graph, then $K(n+2a,r+a)$ is also an odd graph) we get the following.

######  Corollary 13.

If $n$, $r$ and $a$ are positive integers such that $n=2r+1$ and $a\geq 2$,
then

$\rho_{2}(n+2a,r+a)\geq
2^{\left\lfloor\frac{a}{2}\right\rfloor}\rho_{2}(n,r).$

We follow with a version of monotonicity of the $2$-packing number in Kneser
graphs, which turns out to be non-decreasing when both $n$ and $r$ increase by
the same value.

######  Theorem 14.

If $n$ and $r$ are positive integers such that $n\geq 2r+2$, then

$\rho_{2}(n+1,r+1)\geq\rho_{2}(n,r).$

###### Proof.

Note that if $n\geq 3r-1$, then $\rho_{2}(n,r)=1$ and the result is
straightforward. Thus, let us assume $2r+2\leq n\leq 3r-2$. Let $S$ be a
$2$-packing of $K({n,r})$ of size $\rho_{2}(n,r)$. Consider the set:

$T=\Big{\\{}v\cup\\{n+1\\}:\,v\in S\Big{\\}}.$

We have $T\subset V(K(n+1,r+1))$ and $|T|=\rho_{2}(n,r)$. Let us prove that
$T$ is a 2-packing of $K({n+1,r+1})$. In order to do so, since $2(r+1)+1\leq
n+1\leq 3(r+1)-2$, by Observation 10 it is enough to see that $1\leq|u\cap
v|\leq(3(r+1)-1)-(n+1)=3r+1-n$ for any pair of vertices in $T$. In fact, let
$u,v\in T$, and let $\tilde{u}=u\cap[n]$, $\tilde{v}=v\cap[n]$. Since
$\tilde{u},\tilde{v}\in S$, we have $1\leq|\tilde{u}\cap\tilde{v}|\leq
3r-1-n$. As $|u\cap v|=|\tilde{u}\cap\tilde{v}|+1$, the result follows. ∎

######  Lemma 15.

Let $r$, and $t$ be positive integers such that $r\geq 3$ and $2\leq
t\leq\frac{r+3}{3}$. If $\rho_{2}(3r-t,r)\geq 4$, then there exists a
$2$-packing $S$ of $K({3r-t,r})$ with $|S|=4$ and $i_{x}(S)\leq 2$ for every
$x\in[n]$.

###### Proof.

Let $n=3r-t$ and let $S$ be a $2$-packing of $K({n,r})$ with cardinality
$|S|=4$. Note that since $r\geq 3$, we have $\frac{r+3}{3}\leq r-1$. Thus
$2\leq t\leq r-1$ and it follows that $2r+1\leq n\leq 3r-2$. So, by
Observation 10, we have that every pair of vertices in $S$ intersect in at
most $3r-1-n=t-1$ elements. Let us assume $X_{3}^{\geq}(S)\neq\emptyset$ and
let $x\in X_{3}^{\geq}(S)$.

If $x\in X_{3}(S)$, let $u_{1},u_{2},u_{3}$ be the vertices in $S$ that
contain the element $x$ and $u_{4}$ the vertex in $S$ which does not contain
$x$. Note that

$\left|u_{1}\cap X_{2}^{\geq}(S)\right|=\left|\bigcup_{i=2}^{4}(u_{1}\cap
u_{i})\right|\leq 1+\underbrace{\left|(u_{1}\cap
u_{2})\setminus\\{x\\}\right|}_{\leq t-2}+\underbrace{\left|(u_{1}\cap
u_{3})\setminus\\{x\\}\right|}_{\leq t-2}+\underbrace{\left|u_{1}\cap
u_{4}\right|}_{\leq t-1}\leq 3(t-1)-1.$

Thus, since $t\leq\frac{r+3}{3}$, or equivalently $r\geq 3(t-1)$, there is at
least one element $x_{1}\in u_{1}\cap X_{1}(S)$. Analogously, there exist
$x_{2}\in u_{2}\cap X_{1}(S)$ and $x_{3}\in u_{3}\cap X_{1}(S)$. Let us
consider $S^{\prime}=\\{v_{1},v_{2},v_{3},v_{4}\\}$, where

$v_{1}=(u_{1}\setminus\\{x\\})\cup\\{x_{2}\\},\qquad
v_{2}=(u_{2}\setminus\\{x\\})\cup\\{x_{3}\\},\qquad
v_{3}=(u_{3}\setminus\\{x\\})\cup\\{x_{1}\\},\qquad v_{4}=u_{4}.$

It is easy to see that for every $i\neq j$ we have $|u_{i}\cap
u_{j}|=|v_{i}\cap v_{j}|$. Thus, $S^{\prime}$ is a $2$-packing of $K({n,r})$
of size $4$ and $|X_{3}^{\geq}(S^{\prime})|=|X_{3}^{\geq}(S)|-1$.

If $x\in X_{4}(S)$, let $S=\\{u_{1},u_{2},u_{3},u_{4}\\}$. Now we have

$\left|u_{1}\cap X_{2}^{\geq}(S)\right|=\left|\bigcup_{i=2}^{4}(u_{1}\cap
u_{i})\right|\leq 1+\sum_{i=2}^{4}\underbrace{\left|(u_{1}\cap
u_{i})\setminus\\{x\\}\right|}_{\leq t-2}\leq 3(t-1)-2.$

Thus, since $r\geq 3(t-1)$, there is at least two elements
$x_{1}^{1},x_{1}^{2}\in u_{1}\cap X_{1}(S)$. Analogously, there exist
$x_{i}^{1},x_{i}^{2}\in u_{i}\cap X_{1}(S)$ for $i=2,3,4$. Let us consider
$S^{\prime}=\\{v_{1},v_{2},v_{3},v_{4}\\}$, where

$\displaystyle v_{1}=(u_{1}\setminus\\{x\\})\cup\\{x_{4}^{1}\\},$
$\displaystyle v_{2}=(u_{2}\setminus\\{x\\})\cup\\{x_{1}^{1}\\},$
$\displaystyle
v_{3}=(u_{3}\setminus\\{x,x_{3}^{2}\\})\cup\\{x_{1}^{2},x_{2}^{1}\\},$
$\displaystyle
v_{4}=(u_{4}\setminus\\{x,x_{4}^{2}\\})\cup\\{x_{2}^{2},x_{3}^{1}\\}.$

It is easy to see that for every $i\neq j$ we have $|u_{i}\cap
u_{j}|=|v_{i}\cap v_{j}|$. Thus, $S^{\prime}$ is a $2$-packing of $K({n,r})$
of size $4$ and $|X_{3}^{\geq}(S^{\prime})|=|X_{3}^{\geq}(S)|-1$.

In any case, if $X_{3}^{\geq}(S)\neq\emptyset$, we build a $2$-packing
$S^{\prime}$ of size $4$ with $|X_{3}^{\geq}(S^{\prime})|<|X_{3}^{\geq}(S)|$.
If $X_{3}^{\geq}(S^{\prime})\neq\emptyset$, we repeat the procedure until we
get a $2$-packing of four vertices for which each element occurs at most
twice. ∎

We can prove, analogously, the following lemma.

######  Lemma 16.

Let $r$, and $t$ be positive integers such that $r\geq 3$ and $2\leq
t\leq\frac{r+4}{4}$. If $\rho_{2}(3r-t,r)\geq 5$, then there exists a
$2$-packing $S$ of $K({3r-t,r})$ with $|S|=5$ and $i_{x}(S)\leq 2$ for every
$x\in[n]$.

###### Proof.

Let $n=3r-t$ and let $S$ be a $2$-packing of $K({n,r})$ with cardinality
$|S|=5$. Note that since $r\geq 3$, we have $\frac{r+4}{4}<r-1$. Thus $2\leq
t<r-1$ and it follows that $2r+1<n\leq 3r-2$. Then, by Observation 10, every
pair of vertices in $S$ intersect in at most $3r-1-n=t-1$ elements. Let us
assume $X_{3}^{\geq}(S)\neq\emptyset$ and let $x\in X_{3}^{\geq}(S)$.

If $x\in X_{3}(S)\cup X_{4}(S)$, let $u_{1},u_{2},u_{3}$ be vertices in $S$
that contain the element $x$ and $u_{4},u_{5}$ the remaining vertices in $S$
such that $x\notin u_{5}$. Note that

$\left|u_{1}\cap X_{2}^{\geq}(S)\right|=\left|\bigcup_{i=2}^{5}(u_{1}\cap
u_{i})\right|\leq 1+\sum_{i=2,3}\underbrace{\left|(u_{1}\cap
u_{i})\setminus\\{x\\}\right|}_{\leq
t-2}+\sum_{i=4,5}\underbrace{\left|u_{1}\cap u_{i}\right|}_{\leq t-1}\leq
4(t-1)-1.$

Thus, since $t\leq\frac{r+4}{4}$, or equivalently $r\geq 4(t-1)$, there is at
least one element $x_{1}\in u_{1}\cap X_{1}(S)$. Analogously, there exist
$x_{2}\in u_{2}\cap X_{1}(S)$ and $x_{3}\in u_{3}\cap X_{1}(S)$. Let us
consider $S^{\prime}=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$, where

$v_{1}=(u_{1}\setminus\\{x\\})\cup\\{x_{2}\\},\quad
v_{2}=(u_{2}\setminus\\{x\\})\cup\\{x_{3}\\},\quad
v_{3}=(u_{3}\setminus\\{x\\})\cup\\{x_{1}\\},\quad v_{4}=u_{4},\quad
v_{5}=u_{5}.$

Note that if $x\in X_{4}(S)$, then $x\in X_{1}(S^{\prime})$. It is easy to see
that for every $i\neq j$ we have $|u_{i}\cap u_{j}|=|v_{i}\cap v_{j}|$.
Therefore, $S^{\prime}$ is a $2$-packing of $K({n,r})$ of size $5$ and
$|X_{3}^{\geq}(S^{\prime})|=|X_{3}^{\geq}(S)|-1$.

If $x\in X_{5}(S)$, let $S=\\{u_{1},u_{2},u_{3},u_{4},u_{5}\\}$. We have

$\left|u_{1}\cap X_{2}^{\geq}(S)\right|=\left|\bigcup_{i=2}^{5}(u_{1}\cap
u_{i})\right|\leq 1+\sum_{i=2}^{5}\underbrace{\left|(u_{1}\cap
u_{i})\setminus\\{x\\}\right|}_{\leq t-2}\leq 4(t-1)-3.$

Thus, since $r\geq 4(t-1)$, there are at least three elements
$x_{1}^{1},x_{1}^{2},x_{1}^{3}\in u_{1}\cap X_{1}(S)$. Analogously, there
exist $x_{i}^{1},x_{i}^{2},x_{i}^{3}\in u_{i}\cap X_{1}(S)$ for $i=2,3,4,5$.
Let us consider $S^{\prime}=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$, where

$\displaystyle v_{1}=(u_{1}\setminus\\{x\\})\cup\\{x_{5}^{1}\\},$
$\displaystyle v_{2}=(u_{2}\setminus\\{x\\})\cup\\{x_{1}^{1}\\},$
$\displaystyle
v_{3}=(u_{3}\setminus\\{x,x_{3}^{3}\\})\cup\\{x_{1}^{2},x_{2}^{1}\\},$
$\displaystyle
v_{4}=(u_{4}\setminus\\{x,x_{4}^{2},x_{4}^{3}\\})\cup\\{x_{1}^{3},x_{2}^{2},x_{3}^{1}\\},$
$\displaystyle
v_{5}=(u_{5}\setminus\\{x,x_{5}^{2},x_{5}^{3}\\})\cup\\{x_{2}^{3},x_{3}^{2},x_{4}^{1}\\}.$

It can be easily checked that for every $i\neq j$ we have $|u_{i}\cap
u_{j}|=|v_{i}\cap v_{j}|$. It turns out that $S^{\prime}$ is a $2$-packing of
$K({n,r})$ of size $5$ and $|X_{3}^{\geq}(S^{\prime})|=|X_{3}^{\geq}(S)|-1$.

In any case, if $X_{3}^{\geq}(S)\neq\emptyset$, we get a $2$-packing
$S^{\prime}$ of size $5$ with $|X_{3}^{\geq}(S^{\prime})|<|X_{3}^{\geq}(S)|$.
If $X_{3}^{\geq}(S^{\prime})\neq\emptyset$, we repeat the procedure until we
get a $2$-packing of five vertices for which each element occurs at most
twice. ∎

From Proposition 11, and some other results of similar nature, one can suspect
that $\rho_{2}(n,r)$ will be small if $n$ is close to $3r$. The following
result describes how close $n$ has to be to $3r-3$ in order to have
$\rho_{2}(n,r)$ equal to $3$ or $4$.

######  Theorem 17.

If $r$, $n$ and $t$ are positive integers such that $2\leq t\leq r-1$ and
$n=3r-t$, then:

  1. 1.

if $t\leq\frac{r+5}{5}$, then $\rho_{2}(n,r)=3$;

  2. 2.

if $\frac{r+5}{5}<t\leq\frac{2r+9}{9}$, then $\rho_{2}(n,r)=4$.

###### Proof.

  1. 1.

Let us suppose $t\leq\frac{r+5}{5}$, which is equivalent to $r\geq 5(t-1)$.
Assume $\rho_{2}(n,r)\geq 4$ and let $S$ be a packing of $K({n,r})$ of
cardinality $4$. Note that since $r\geq 5(t-1)>3(t-1)$, we have $2\leq
t\leq\frac{r+3}{3}$ and $r\geq 3$. Thus, by Lemma 15, we may consider a
$2$-packing $S$ for which $i_{x}(S)\leq 2$ for every $x\in[n]$. Let us note
that by Observation 10 we have $|u\cap v|\leq t-1$ for each $u,v\in S$, and it
follows

$|X_{2}(S)|=\sum_{{\begin{subarray}{c}u,v\in S\\\ u\neq
v\end{subarray}}}\underbrace{|u\cap v|}_{\leq
t-1}\leq\binom{4}{2}(t-1)=6(t-1).$

On the other hand, since $|X_{1}(S)|\leq n-|X_{2}(S)|$, we have

$\begin{array}[]{lcl}\displaystyle{4r=|S|r=\sum_{x\in[n]}i_{x}(S)}&=&2|X_{2}(S)|+|X_{1}(S)|\\\
&\leq&n+|X_{2}(S)|\\\ &\leq&n+6(t-1)\\\ &\leq&3r+5t-6.\end{array}$

Thus, $r\leq 5(t-1)-1$ and we arise to a contradiction since $r\geq 5(t-1)$.
Therefore $\rho_{2}(n,r)\leq 3$. In order to see that it is equal to $3$ it is
enough to consider the set $S$ given by $S=\\{u_{1},u_{2},u_{3}\\}$ where

$u_{1}=[r],\quad u_{2}=[t-1]\cup[(r+1)..(2r-t+1)],\quad
u_{3}=\\{1\\}\cup[(2r-t+1)..(3r-t)].$

We have $|u_{1}\cap u_{2}|=t-1$ and $|u_{1}\cap u_{3}|=|u_{2}\cap u_{3}|=1$.
So, $S$ is a 2-packing and $\rho_{2}(n,r)=3$.

  2. 2.

Now, let us suppose $\frac{r+5}{5}<t\leq\frac{2r+9}{9}$, which is equivalent
to $\frac{9}{2}(t-1)\leq r<5(t-1)$. Assume $\rho_{2}(n,r)\geq 5$ and let $S$
be a packing of $K({n,r})$ of size $5$. Note that since
$r\geq\frac{9}{2}(t-1)>4(t-1)$, we have $2\leq t\leq\frac{r+4}{4}$ and $r\geq
3$. Thus, by Lemma 16, we may consider a $2$-packing $S$ for which
$i_{x}(S)\leq 2$ for every $x\in[n]$. By Observation 10 we have $|u\cap v|\leq
t-1$ for each $u,v\in S$. Consequently,

$|X_{2}(S)|=\sum_{{\begin{subarray}{c}u,v\in S\\\ u\neq
v\end{subarray}}}\underbrace{|u\cap v|}_{\leq
t-1}\leq\binom{5}{2}(t-1)=10(t-1).$

It follows that

$\begin{array}[]{lcl}\displaystyle{5r=|S|r=\sum_{x\in[n]}i_{x}(S)}&=&2|X_{2}(S)|+|X_{1}(S)|\\\
&\leq&n+|X_{2}(S)|\\\ &\leq&n+10(t-1)=3r+9t-10.\end{array}$

Thus, $r\leq\frac{9}{2}(t-1)-\frac{1}{2}$ and we arise to a contradiction
since $r\geq\frac{9}{2}(t-1)$. Therefore $\rho_{2}(n,r)\leq 4$. In order to
see that it is equal to $4$ it is enough to consider the set $S$ given by
$S=\\{u_{1},u_{2},u_{3},u_{4}\\}$ where

$\displaystyle u_{1}$ $\displaystyle=A_{12}\cup A_{13}\cup A_{14}\cup B_{1}$
$\displaystyle u_{2}$ $\displaystyle=A_{12}\cup A_{23}\cup A_{24}\cup B_{2}$
$\displaystyle u_{3}$ $\displaystyle=A_{13}\cup A_{23}\cup A_{34}\cup B_{3}$
$\displaystyle u_{4}$ $\displaystyle=A_{14}\cup A_{24}\cup A_{34}\cup B_{4}$

where the sets in $\big{\\{}\\{A_{ij}\\}_{i\neq
j}\cup\\{B_{i}\\}_{i=1}^{4}\big{\\}}$ are pairwise disjoint with
$|A_{ij}|=t-1$, and $|B_{i}|=r-3(t-1)$. Note that this is possible since

$6(t-1)+4(r-3(t-1))=4r-6(t-1)=\underbrace{(3r-t)}_{=n}+\underbrace{(r-(5t-6))}_{\leq
0}\leq n.$

We have $|u_{i}\cap u_{j}|=t-1$ for every $i\neq j$. So, $S$ is a packing and
$\rho_{2}(n,r)=4$.

∎

######  Corollary 18.

If $\frac{14}{5}r-1\leq n\leq 3r-2$, then $\rho_{2}(n,r)=3$.

######  Corollary 19.

If $\frac{25}{9}r-1\leq n<\frac{14}{5}r-1$, then $\rho_{2}(n,r)=4$.

##  5 Concluding remarks

In Section 2, we proved that $\gamma_{k}$ is monotonically decreasing, where
$r$ is fixed and $n\geq 2(k+r)$ is growing. We wonder if the lower bound on
$n$ could be improved, and pose the following question.

######  Problem 20.

Is there an integer $n_{0}$, where $n_{0}<2(k+r)$, such that for any $n\geq
n_{0}$, we have $\gamma_{k}(n,r)\geq\gamma_{k}(n+1,r)$?

In Section 3, we established exact values of $\gamma_{k}(n,r)$ and
$\gamma_{t\times k}(n,r)$ for all $n$, where $n\geq r(k+r)-1$. It is thus
natural to ask what are the values of these two invariants when $n$ is smaller
than $r(k+r)-1$. In particular, the most interesting case seems to be that of
odd graphs, that is, when $n=2r+1$.

######  Problem 21.

Determine or provide upper and lower bounds on $\gamma_{k}(2r+1,r)$,
$\gamma_{\times k}(2r+1,r)$ and $\gamma_{t\times k}(2r+1,r)$, for $r>2$.

We mentioned an open problem in Section 4, which is concerned with the exact
values of $\rho_{2}(3r-3,r)$ where $r\leq 8$ (recall that for $r\geq 9$, we
already established the values of $\rho_{2}(3r-3,r)$).

######  Problem 22.

Is it true that the lower bounds in Table 2 are in fact exact values of
$\rho_{2}(3r-3,r)$, where $r\leq 8$.

Regarding the 2-packing number of odd graphs $K(2r+1,r)$, we have proved in
Proposition 12 that $\rho_{2}(2r^{\prime}+1,r^{\prime})\geq
C\cdot\rho_{2}(2r+1,r)$ when $r^{\prime}>r+1$, where $C=2$. In [4] it is shown
that $\rho_{2}(7,3)=7$ and $\rho_{2}(11,5)=66$. So, we wonder whether this $C$
could be improved.

######  Problem 23.

Is there some $C(r)>2$ such that $\rho_{2}(2(r+2)+1,r+2)\geq
C(r)\rho_{2}(2r+1,r)$ holds for all $r\geq 2$?

## Acknowledgments

The first and the third author were supported by the Slovenian Research and
Innovation agency (grants P1-0297, J1-2452, J1-3002, and J1-4008). The second
author was partially supported by the Argentinian National Agency for the
Promotion of Research, Technological Development and Innovation (grant
PICT-2020-03032), the Argentinian National Council for Scientific and
Technical Research (grant PIP CONICET 1900) and the National University of
Rosario (grant PID 80020210300068UR). Research of the fourth author was
supported in part by the South African National Research Foundation under
grant number 132588 and the University of Johannesburg. The second and fourth
authors thank the University of Maribor for their hospitality.

## References

  * Bonomo et al., [2018] Bonomo, F., Brešar, B., Grippo, L. N., Milanič, M., and Safe, M. D. (2018).  Domination parameters with number 2: interrelations and algorithmic consequences.  Discrete Appl. Math., 235:23–50.
  * Brešar et al., [2019] Brešar, B., Kos, T., and Torres, P. D. (2019).  Grundy domination and zero forcing in Kneser graphs.  Ars Math. Contemp., 17(2):419–430.
  * Chellali et al., [2012] Chellali, M., Favaron, O., Hansberg, A., and Volkmann, L. (2012).  k-domination and k-independence in graphs: A survey.  Graphs Combin., 28(1):1–55.
  * Cornet and Torres, [2023] Cornet, M. G. and Torres, P. (2023).  $k$-tuple domination on Kneser graphs.  arXiv preprint arXiv:2308.15603.
  * Erdős et al., [1961] Erdős, P., Ko, C., and Rado, R. (1961).  Intersection theorems for systems of finite sets.  Quart. J. Math. Oxford Ser. (2), 12:313–320.
  * [6] Fink, J. F. and Jacobson, M. S. (1985a).  n-domination in graphs.  In Graph theory with applications to algorithms and computer science, pages 282–300. Wiley.
  * [7] Fink, J. F. and Jacobson, M. S. (1985b).  On n-domination, n-dependence and forbidden subgraphs.  In Graph theory with applications to algorithms and computer science, pages 301–311. Wiley.
  * Gorodezky, [2007] Gorodezky, I. (2007).  Dominating sets in Kneser graphs.  Master’s thesis, University of Waterloo.
  * Hansberg and Volkmann, [2020] Hansberg, A. and Volkmann, L. (2020).  Multiple domination.  In Topics in domination in graphs, pages 151–203. Springer.
  * Harary and Haynes, [2000] Harary, F. and Haynes, T. W. (2000).  Double domination in graphs.  Ars combinatoria, 55:201–213.
  * Haynes et al., [2020] Haynes, T. W., Hedetniemi, S. T., and Henning, M. A., editors ([2020] ©2020).  Topics in domination in graphs, volume 64 of Developments in Mathematics.  Springer, Cham.
  * Haynes et al., [2021] Haynes, T. W., Hedetniemi, S. T., and Henning, M. A., editors ([2021] ©2021).  Structures of domination in graphs, volume 66 of Developments in Mathematics.  Springer, Cham.
  * Haynes et al., [2023] Haynes, T. W., Hedetniemi, S. T., and Henning, M. A. ([2023] ©2023).  Domination in graphs—core concepts.  Springer Monographs in Mathematics. Springer, Cham.
  * Henning and Kazemi, [2010] Henning, M. A. and Kazemi, A. P. (2010).  $k$-tuple total domination in graphs.  Discrete Appl. Math., 158(9):1006–1011.
  * Henning and Yeo, [2010] Henning, M. A. and Yeo, A. (2010).  Strong transversals in hypergraphs and double total domination in graphs.  SIAM J. Discrete Math., 24(4):1336–1355.
  * Henning and Yeo, [2013] Henning, M. A. and Yeo, A. (2013).  Total domination in graphs.  Springer Monographs in Mathematics. Springer, New York.
  * Ivančo and Zelinka, [1993] Ivančo, J. and Zelinka, B. (1993).  Domination in Kneser graphs.  Math. Bohem., 118(2):147–152.
  * Lovász, [1978] Lovász, L. (1978).  Kneser’s conjecture, chromatic number, and homotopy.  J. Combin. Theory Ser. A, 25(3):319–324.
  * Östergård et al., [2014] Östergård, P. R., Shao, Z., and Xu, X. (2014).  Bounds on the domination number of Kneser graphs.  Ars Math. Contemp., 9(2):187–195.
  * Valencia-Pabon and Vera, [2005] Valencia-Pabon, M. and Vera, J.-C. (2005).  On the diameter of Kneser graphs.  Discrete math., 305:383–385.
  * Zec and Grbić, [2023] Zec, T. and Grbić, M. (2023).  Several Roman domination graph invariants on Kneser graphs.  Discrete Math. Theor. Comput. Sci., 25(1):Paper No. 14, 18.


11institutetext: Department of Mathematical Sciences, Sharif University of
Technology, Tehran, Iran

# Recognizing Visibility Graphs of Polygons with Holes and Internal-External
Visibility Graphs of Polygons

Hossein Boomari 11 Mojtaba Ostovari 11 Alireza Zarei 11

###### Abstract

Visibility graph of a polygon corresponds to its internal diagonals and
boundary edges. For each vertex on the boundary of the polygon, we have a
vertex in this graph and if two vertices of the polygon see each other there
is an edge between their corresponding vertices in the graph. Two vertices of
a polygon see each other if and only if their connecting line segment
completely lies inside the polygon, and they are externally visible if and
only if this line segment completely lies outside the polygon. Recognizing
visibility graphs is the problem of deciding whether there is a simple polygon
whose visibility graph is isomorphic to a given input graph. This problem is
well-known and well-studied, but yet widely open in geometric graphs and
computational geometry.

Existential Theory of the Reals is the complexity class of problems that can
be reduced to the problem of deciding whether there exists a solution to a
quantifier-free formula $F(X_{1},X_{2},...,X_{n})$, involving equalities and
inequalities of real polynomials with real variables. The complete problems
for this complexity class are called $\exists\mathbb{R}-Complete$.

In this paper we show that recognizing visibility graphs of polygons with
holes is $\exists\mathbb{R}-Complete$. Moreover, we show that recognizing
visibility graphs of simple polygons when we have the internal and external
visibility graphs, is also $\exists\mathbb{R}-Complete$.

###### Keywords:

Visibility graph; polygon with holes, external visibility; recognizing
visibility graph; existential theory of the reals.

##  1 Introduction

The visibility graph of a simple planar polygon is a graph in which there is a
vertex for each vertex of the polygon and for each pair of visible vertices of
the polygon there is an edge between their corresponding vertices in this
graph. Two points in a simple polygon are internally (resp. externally)
visible from each other if and only if their connecting segment completely
lies inside (resp. outside) the polygon. In this definition, each pair of
adjacent vertices on the boundary of the polygon are assumed to be visible
from each other. This implies that we always have a Hamiltonian cycle in a
visibility graph which determines the order of vertices on the boundary of the
corresponding polygon. A polygon with holes has some non-intersecting holes
inside the boundary of the polygon. In these polygons the area inside a hole
is considered as the outside area and internal and external visibility graphs
of such polygons are defined in the same way as defined for simple polygons.
In the visibility graph of a polygon with holes, we have the sequence of
vertices corresponding to the boundary of each hole, as well.

Computing the visibility graph of a given simple polygon has many applications
in computer graphics [18], computational geometry [13] and robotics [4]. There
are several efficient polynomial time algorithms for this problem [13].

This concept has been studied in reverse as well: Is there any simple polygon
whose visibility graph is isomorphic to a given graph, and, if there is such a
polygon, is there any way to reconstruct it(finding positions for its vertices
in the plane)? The former problem is known as recognizing visibility graphs
and the latter one is known as reconstructing a polygon from a visibility
graph. The computational complexity of both these problems are widely open.
The only known result about the computational complexity of these problems is
that they belong to PSPACE [9] complexity class. More precisely, they belong
to the class of Existential theory of the reals [15]. This means that it is
not even known whether these problems are in NP or can be solved in polynomial
time. Even, if we are given the Hamiltonian cycle of the visibility graph
which determines the order of vertices on the boundary of the target polygon,
the exact complexity class of these problems are still unknown.

However, these problems have been solved efficiently for special cases of
tower and spiral polygons. A tower polygon consists of two concave chains on
its boundary whose share one vertex and their other endpoints are connected by
a segment. A spiral polygon has exactly one concave and one convex chain on
its boundary. The recognizing and reconstruction problems have been solved for
tower polygons [8] and spiral polygons [10] in linear time in terms of the
size of the graph.

Although there is some progress on recognizing and reconstruction problems,
there have been plenty of studies on characterizing visibility graphs. In
1988, Ghosh introduced three necessary conditions for visibility graphs and
conjectured their sufficiency [11]. In 1990, Everett proposed a graph that
rejects Ghosh’s conjecture [9]. She also refined Ghosh’s third necessary
condition to a new stronger one [12]. In 1992, Abello et al. built a graph
satisfying Ghosh’s conditions and the stronger version of the third condition
which was not the visibility graph of any simple polygon [3], disproving the
sufficiency of these conditions. In 1997, Ghosh added his forth necessary
condition and conjectured that this condition along with his first two
conditions and the stronger version of the third condition are sufficient for
a graph to be a visibility graph. Finally, in 2005 Streinu proposed a counter
example for this conjecture [17]. Independently, in 1994, Abello et al.
proposed the notion of q-persistant graphs, which includes the visibility
graph and BlockingVertexAssignment. The BlockingVertexAssignment is a proper
function from invisible pairs to their blocking vertex that satifies four
conditions. They proved that each visibility graph has at least one blocking
vertex assignment. They conjectured that these constraints are verifiable
efficiently [1]. But, the computational complexity of verifying the existance
of a blocking vertex assignment or finding such a function in a visibility
graph, are not known to be solvable in polynomial time. Later in 1995, Abello
et al. added one more constraint to these constraints and proved their
sufficiency for recognition and reconstruction of 2-spiral polygons111polygons
with at most 2 concave chains. moreover, for a given graph, its Hamiltonian
cycle and a blocking vertex assignment that satisfy these constraints, they
proposed an efficient method for recognition and reconstruction problems for
2-spiral polygons, efficiently [2]. But by now, there is no efficient
algorithm for obtaining a BlockingVertexAssignment for 2-spiral polygons from
which the recognizing and reconstruction problems could be solved efficiently
for this type of polygons.

Existential theory of the reals ($\exists\mathbb{R}$) is a complexity class
that introduced in 1989 [5] and defined by Shor in 1991 [16]. It is the
complexity class of problems which can be reduced to the problem of deciding,
whether there is a solution for a Boolean formula
$\phi:\\{True,False\\}^{n}\rightarrow\\{True,False\\}$ in propositional logic,
in the form
$\phi(F_{1}(X_{1},X_{2},...,X_{N}),F_{2}(X_{1},X_{2},...,X_{N}),...,F_{n}(X_{1},X_{2},...,X_{N}))$,
where each $F_{i}:\mathbb{R}^{N}\rightarrow\\{True,False\\}$ consists of a
polynomial function $G_{i}:\mathbb{R}^{N}:\rightarrow\mathbb{R}$ on some real
variables, compared to $0$ with one of the comparison operators in
$\\{<,\leq,=,>,\geq\\}$ (for example
$G_{i}(X_{1},X_{2})=X_{1}^{3}X_{2}^{2}-X_{1}X_{2}^{3}$ and
$F_{i}(X_{1},X_{2})\equiv G_{i}(X_{1},X_{2})<0$). Clearly, satisfiability of
quantifier free Boolean formula belongs to $\exists\mathbb{R}$. Therefore,
$\exists\mathbb{R}$ includes all $NP$ problems. In addition,
$\exists\mathbb{R}$ strictly belongs to $PSPACE$ [15] and we have
$NP\subseteq\exists\mathbb{R}\subset PSPACE$. Many other decision problems,
specially geometric problems, belongs to $\exists\mathbb{R}$ and some are
complete for this complexity class. Recognizing LineArrangement
(Stretchability), simple order type, intersection graph of segments, and
intersection graph of unit disks in the plane are some problems which are
complete for $\exists\mathbb{R}$ or simply $\exists\mathbb{R}-Complete$ [6].
As the most related result to this paper, in 2017 Cardinal et al. showed that
recognizing visibility graph of a point set is $\exists\mathbb{R}-Complete$
[7]. Computational complexity of these problems was open for years and after
proving $\exists\mathbb{R}-Completeness$, the study of $\exists\mathbb{R}$
class and $\exists\mathbb{R}-Complete$ problems gets more attention in
computational geometry literature. We discuss Recognizing LineArrangement
(Stretchability) problem with more details in this paper in Section 2.

In this paper, we show that recognizing visibility graph of a polygon with
holes is $\exists\mathbb{R}-Complete$. Also, we show that recognizing
visibility graph of a simply polygon having both its internal and external
visibility graphs is $\exists\mathbb{R}-Complete$. In both problems we assume
that the sequence of vertices corresponding to the boundary of the polygon and
its holes, are given as input.

##  2 Preliminaries and Definitions

In this section, we give a brief survey on Ghosh’s necessary conditions for a
visibility graph and describe the problems of recognizing LineArrangement and
Stretchability in the plane. We need these details in some parts of our
proofs. At the end of this section, we introduce some definition and basic
facts to be used in next sections.

###  2.1 Ghosh’s necessary conditions

As stated before, there are are 4 necessary but not sufficient conditions that
a graph must have to be the visibility graph of a simple polygon. These
conditions are defined on the input visibility graph and a Hamiltonian cycle
which is assumed to be the order of vertices on the boundary of the target
polygon. We review first two conditions here, briefly.

####  2.1.1 First necessary condition

Each ordered cycle of the visibility graph of length more than three, has some
chords. The order of vertices in such a cycle must follow the Hamiltonian
cycle, and a chord is an edge between two non-adjacent vertices of the cycle.
This condition is a consequence of the fact that each simple polygon has a
triangulation.

####  2.1.2 Second necessary condition

Each invisible pair of vertices has a blocking vertex. A vertex $o$ in a
visibility graph is a blocking vertex for an invisible pair of vertices
$(p,q)$, if all vertices between $p$ and $o$ (including $p$), on the
Hamiltonian cycle, are invisible to all vertices between $o$ and $q$
(including $q$).

###### Observation 1

For an invisible pair $(p,q)$, there is at least one and at most two blocking
vertices which are visible from $p$. These candidates are the last visible
vertices in a clockwise and counter-clockwise walk, from $p$ toward $q$ along
the Hamiltonian cycle.

###### Observation 2

For an invisible pair $(p,q)$, if the last visible vertex from $p$ in the
clockwise walk from $p$ toward $q$ is further to $p$ than the last visible
vertex from $q$ in the counter-clockwise walk from $q$ toward $p$, there is no
blocking vertex for this invisible pair in the clockwise walk from $p$ to $q$.

###  2.2 Line arrangement and stretchability

Considering a set of lines in the plane, the problem of describing the
configuration of these lines and their arrangement is called
PlaneConfiguration. This is an important and fundamental problem in
combinatorics and a well-studied problem in computational geometry.
LineArrangement is a way to describe this configuration. This description for
a set of lines $l_{1},l_{2},...,l_{n}$ consists of their vertical order with
respect to a vertical line to the left of all their intersections, and for
each line $l_{i}$, the order of lines that are intersected by $l_{i}$ when we
traverse $l_{i}$ from left to right (we assume that none of the input lines
$l_{i}$ is vertical). Recognizing whether there can be a set of lines in the
plane with the given Line Arragement, is called Recognizing LineArrangement or
simply LineArrangement problem. When the lines are in general position (all
pairs of lines intersect and no 3 lines intersect at the same point) the
problem is called SimpleLineArrangement. It has been proved that
SimpleLineArrangement is $\exists\mathbb{R}-Complete$ [6].

A pseudo line is a monotone curve with respect to the $X$ axis. Assuming that
no pair of pseudo lines intersect each other more than once, we can describe
an instance of recognizing PseudoLineArrangement problem in the same way as we
did for LineArrangement. However, Recognizing PseudoLineArrangement belongs to
the $P$ complexity class and it can be decided with a Turing machine in
polynomial time [14]. Because we need such a realization algorithm, we have
gave a pseudo code implementation of this algorithm in Algorithm 1 in Appendix
0.B.

In this algorithm we reconstruct each pseudo line as a chain of line segments
in the plane. This algorithm receives as input, the initial vertical order of
pseudo lines and for each pseudo line, a queue that contains the order of
intersections of this pseudo line with other pseudo lines from left to right.
There is no duplicate member in a queue $S_{i}$, otherwise, $l_{i}$ must
intersect another pseudo line $l_{j}$ more than once which is a contradiction
and in these cases the algorithm rejects the input. The algorithm starts with
$n$ queues, $L^{\prime}_{i}s$, each of which will contain the sequence of
vertices of the corresponding chain of the pseudo line $l_{i}$ and has $(0,i)$
as the initial point of $l_{i}$. Then, in each step, the algorithm finds two
pseudo lines that intersect and swaps their order along an imaginary vertical
sweep line that moves from left to right. This algorithm, for each
intersection between a pair of pseudo lines $l_{p}$ and $l_{q}$, adds three
points to $L_{p}$ and $L_{q}$ to swap their order(See Fig. 1-b). When the
algorithm cannot find a proper pair of pseudo lines to swap, it means that the
input is not recognizable and input is rejected. As Fig. 1-c shows, when there
is more than one choice for $(p,q)$, any one can be selected and it does not
affect the rest of the algorithm.

This algorithm recognizes and reconstructs a PseudoLineArrangement in
polynomial time and obtains a set of pseudo lines, which their break-points do
not necessarily correspond to their intersections. For example, point $P$ in
Fig. 1-b is not an intersection between the pseudo lines. It is simple to
verify that we can simply remove these non-intersection break-points from the
pseudo lines without violating input configuration constraints. Fig. 1-d shows
how removing these extra break-points from the chains produces, new
PseudoLineArrangement which have the same order of intersections as the input
configuration.

Trivially, if an instance of the LineArrangement problem is realizable, it has
a PseudoLineArrangement realization as well. On the other hand, if an instance
of the pseudo LineArrangement has a realization in which all segments of each
pseudo line lie on the same line, the input instance has also a
LineArrangement realization as well.

Figure 1: The reconstruction algorithm for PseodoLineArrangement.

Therefore, we can describe the LineArrangement problem as follows:

  * •

Is it possible to stretch a PseudoLineArrangement of a given line arragement
description such that each pseudo line lies on a single line?

This problem is known as ”Stretchability”. As stated before, pseudo line
arragement belongs to the $P$ complexity class and can be recognized and
reconstructed efficiently(Algorithm 1). Therefore,
$\exists\mathbb{R}-Completeness$ of LineArrangement implies that the
stretchability is $\exists\mathbb{R}-Complete$.

###  2.3 Visibility graph of a polygon with holes

A polygon with holes is a simple polygon that has a set of non-colliding holes
(simple polygons) inside it. The internal areas of the holes belong to the
outside area of the polygon. In these polygons, two vertices are visible from
each other if their connecting segment completely lies inside the polygon.
Visibility graph of a polygon with holes is a graph whose vertices correspond
to vertices of the polygon and holes, and in this graph there is an edge
between two vertices if and only if their corresponding vertices in the
polygon are visible from each other (see Fig. 2). In this paper, we assume
that along with the visibility graph, we have the cycles that correspond to
the order of vertices on the boundary of the polygon and the holes. The cycle
that corresponds to the external boundary of the polygon is called the
external cycle(see Fig. 2).

Figure 2: A polygon with one hole (a), and its visibility graph (b).

###  2.4 Internal-external visibility graphs

When we say that two points of a polygon are visible, it means that they see
each other inside the polygon. However, the visibility can be defined
similarly for the outside of the polygon. When we are going to talk about both
of these visibilities, the former is called internal visibility and the latter
is called the external visibility. Precisely, two vertices are externally
visible to each other if their connecting segment lies outside the polygon.
Similarly, external visibility graph of a polygon is a graph whose vertices
correspond to the vertices of the polygon, and its edges correspond to the
external visibility. Having both these graphs separately is the internal-
external visibility graphs of a polygon(See Fig. 3).

Figure 3: A polygon (a) and its internal (b) and external (c) visibility
graphs.

##  3 Complexity of Recognizing Visibility Graphs of Polygons with Holes

In this section, we show that recognizing visibility graph of a polygon with
holes is $\exists\mathbb{R}-Complete$. This is done by reducing an instance of
the stretchability problem to an instance of this problem.

In Section 2.2 we showed that we can describe the line arragement problem as
an instance of stretchability of pseudo lines in which each pseudo line is
composed of a chain of segments and the break-points of these chains(except
the first and the last endpoints of the chains) correspond to the intersection
points of the pseudo lines. We build a visibility graph $\mathcal{G}$, an
external cycle $\mathcal{P}$, and a set of boundary cycles $\mathcal{H}$ from
an instance of such a stretchability problem, and prove that the pseudo line
arragement is stretchable in the plane if and only if there exists a polygon
with holes whose visibility graph is $\mathcal{G}$, its external cycle is
$\mathcal{P}$ and the set of boundary cycles of its holes is $\mathcal{H}$.

Assume that $(\mathcal{L},\mathcal{S})$ is an instance of the stretchability
problem where, as described in Algorithm 1, $\mathcal{L}=\langle
l_{1},l_{2},...,l_{n}\rangle$ is the sequence of the pseudo lines and
$\mathcal{S}=\langle S_{1},S_{2},...,S_{n}\rangle$ is the sequence of the
intersections of these pseudo lines in which $S_{i}=\langle
l_{a(i,1),...,a(i,n-1)}\rangle$ is the order of lines intersected by $l_{i}$.
Lets denote by $(\mathcal{G},\mathcal{P},\mathcal{H})$ the corresponding
instance of the visibility graph realization in which $\mathcal{G}$ is the
visibility graph, $\mathcal{P}$ is the external cycle of the outer boundary of
the polygon and $\mathcal{H}=\\{H_{1},H_{2},...,H_{k}\\}$ is the set of
boundary cycles of its holes. To build this instance, consider an example of
such $(\mathcal{L},\mathcal{S})$ instance shown in Fig. 4-a. This figure shows
a pseudo line realization obtained from Algorithm 1 for an instance of four
pseudo lines. If this instance is stretchable, like the one shown in Fig. 4-b,
we can build a polygon with holes like the one shown in Fig. 4-c. The outer
boundary of this polygon and the boundary of its holes lie along a set of
convex curves connecting the endpoints of each stretched pseudo line.
Precisely, for each stretched pseudo line $l_{i}$, as in Fig. 4-b, there is a
pair of convex chains in its both sides which connect its endpoints. This pair
of pseudo lines are sufficiently close to their corresponding stretched pseudo
lines, and their break-points are the intersection points of these chains(like
point $o$ in Fig. 4-c). This pair of convex chains, for each pseudo line
$l_{i}$, make a convex polygon which is called its channel and is denoted by
$Ch(l_{i})$. The outer boundary of the target polygon and the boundary of its
holes are obtains by removing those segments of the chains that lie inside
another channel (see Fig. 4-c). Note that, we do not have the stretched
realization of the $(\mathcal{L},\mathcal{S})$ instance of stretachability
problem. But, from the pseudo line realization, we can determine
$\mathcal{G}$, $\mathcal{P}$ and $\mathcal{H}$ of the corresponding instance
$(\mathcal{G},\mathcal{P},\mathcal{H})$ in polynomial time. As shown in Fig.
4-d, $\mathcal{P}$ and $\mathcal{H}$ are obtained by imaginary drawing the
channel for each pseudo line $l_{i}$. Finnaly the vertex set of graph
$\mathcal{G}$ is the set of all break-points of these convex chains and two
vertices are connected by an edge if and only if they belong to the boundary
of the same channel. The following theorem shows the relationship between
$(\mathcal{L},\mathcal{S})$ and $(\mathcal{G},\mathcal{P},\mathcal{H})$
problem instances.

Figure 4: A polygon with holes which is constructed from an instance of the
PseudoLineArrangement problem.

###### Theorem 3.1

An instance $(\mathcal{L},\mathcal{S})$ of the stretchability problem is
realizable if and only if its corresponding
$(\mathcal{G},\mathcal{P},\mathcal{H})$ instance of the visibility graph is
recognizable.

###### Proof

When $(\mathcal{L},\mathcal{S})$ is stretchable, we can obtain a polygon with
holes from the realization of $(\mathcal{L},\mathcal{S})$ whose external and
holes boundaries are respectively correspond to $\mathcal{P}$ and
$\mathcal{H}$. On the other hand, when the channels are sufficiently narrow
and close to their line segments, each pair of vertices see each other if and
only if they belong to the same channel. This means that their visibiliy graph
is $\mathcal{G}$ and this polygon with holes is a realization for
$(\mathcal{G},\mathcal{P},\mathcal{H})$ instance.

To prove the theorem in reverse, assume that the instance
$(\mathcal{G},\mathcal{P},\mathcal{H})$ is realizable and we have a polygon
$\mathcal{P}$ with holes $\mathcal{H}$ whose visibility graph is
$\mathcal{G}$. In this realization the endpoints of each channel are connected
by a line. We claim that this set of lines is an answer for the
$(\mathcal{L},\mathcal{S})$ instance.

The induced subgraph of $\mathcal{G}$ on the vertices of a channel $C$ is a
complete graph which implies that in the realization of
$(\mathcal{G},\mathcal{P},\mathcal{H})$ these vertices must lie on the
boundary of a convex polygon. On the other hand, each pair of channels $C_{i}$
and $C_{j}$ has exactly four vertices in common. Denote these common vertices
by $Int(C_{i},C_{j})$. This set of common vertices forces that their
corresponding lines must intersect in a point. Therefore, each pair of the
obtained lines intersect in a point. To complete the proof, we must show that
the intersections of these lines follow $\mathcal{S}$ and their initial
vertical order is as $\mathcal{L}$. Consider the corresponding line of a
channel $C$. The order of intersection points of this line and corresponding
lines of other channels is directly derived from the order of common vertices
between $C$ and other channels along the boundary of $C$. While these common
vertices are either the vertices of $\mathcal{P}$ or cycles in $\mathcal{H}$
we can identify their order uniquely along the boundary of channel $C$. To do
this, we first obtain the common vertices $Int(C,C_{i})$, which have two
vertices on $\mathcal{P}$ which are connected to an endpoint of the channel
$C$. This determines the first intersection point on the corresponding line of
channel $C$. Let $p,q$ be the other vertices in $Int(C,C_{i})$. These vertices
either belong to $\mathcal{P}$ or a cycle in $\mathcal{H}$ and in both cases
the next intersected channel is determined. When $p$ lies on $\mathcal{P}$,
the next intersected channel is $C_{j}$ where $Int(C,C_{j})$ has a vertex
adjacent to $p$ in $\mathcal{P}$, and when $p$ lies on a cycle
$H\in\mathcal{H}$, the next intersected channel is $C_{j}$ where
$Int(C,C_{j})$ has a vertex adjacent to $p$ in $H$. Continuing this procedure,
the order of intersection points of the corresponding line of the channel $C$
are obtained which exactly is the same as $\mathcal{S}$. Finally, the initial
order of these lines is the same as the order of endpoints of their
corresponding channels along $\mathcal{P}$. Therefore, the initial vertical
order of these lines will follow $\mathcal{L}$ by properly rotating the
realization of the polygon for $(\mathcal{G},\mathcal{P},\mathcal{H})$.

It is easy to show that recognizing visibility graph of polygon with holes
belong to $\exists\mathbb{R}$. While the stretchability problem is
$\exists\mathbb{R}-Complete$ and our reduction is polynomial, Theorem 3.1
implies the $\exists\mathbb{R}-Hardness$ of recognizing visibility graph of
polygon with holes. Therefore, we have the following theorem.

###### Theorem 3.2

Recognizing visibility graph of polygon with holes is
$\exists\mathbb{R}-Complete$.

##  4 Complexity of Internal-External Visibility Graphs of a Simple Polygon

In this section, we show that recognizing internal-external visibility graph
of a simple polygon is $\exists\mathbb{R}-Complete$. Again, we prove this by
reducing an instance $(\mathcal{L},\mathcal{S})$ of the stretchability problem
to an instance $(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ of the
visibility graph recognition where $\mathcal{G}_{int}$ and $\mathcal{G}_{ext}$
are respectively the internal and external visibility graphs and $\mathcal{P}$
is the external cycle of the boundary of the target simple polygon. Our
construction of $(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ is similar
to the construction described in Section 3. We first build the same polygon
with holes as in Section 3 with this difference that on each segment $ab$ on
the boundary of a hole in $\mathcal{H}$, which $a$ and $b$ are intersection
points of two convex chains, another point $c$ is added(Fig. 5-a) without
violating the convexity of the channel chains. Then, we connect the holes
together and to the external area to remove the holes and obtain a simple
polygon. This is done iteratively on each hole by adding a pair of parallel
and sufficiently close cut edges that connect a boundary segment of a hole to
a segment of the current outer boundary. These segments must belong to
different chains of the same channel. These cut edges act as cutting channels
like Fig. 5-b. Trivially, the visibility graph of this simple polygon is no
longer the same as the one obtained in Section 3. Having the stretched
realization, we can compute internal and external visibility graphs of this
simple polygon, which mainly depends on the way we cut the channels to remove
the holes. In this polygon, two vertices are internally visible if and only if
they belong to the same channel and their connecting segment does not cross a
cut edge. In the external visibility graph, two vertices have an edge if and
only if one of the following conditions hold:

  * •

they are adjacent vertices on $\mathcal{P}$(points $a$ and $b$ in Fig. 5-b),

  * •

they are endpoints of the edges of the same cut(points $c$ and $d$ in Fig.
5-b),

  * •

they are vertices on different channel chains of the same hole (holes before
cutting)(points $e$ and $f$ in Fig. 5-b),

  * •

they lie on different channel chains and between two consecutive endpoints of
the channels on $\mathcal{P}$(before cutting but including cut
vertices)(points $g$ and $h$ or $g$ and $i$).

Figure 5: A simple polygon constructed from an instance of the
PseudoLineArrangement problem.

Trivially, if $(\mathcal{L},\mathcal{S})$ is stretchable, its corresponding
instance $(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ is recognizable.
To prove the reverse equivalence, we show in the next theorem that in any
realization of $(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ the
boundary vertices of each channel is a convex polygon. Then, by an argument
similar to the one in Theorem 3.1, the stretchability of
$(\mathcal{L},\mathcal{S})$ is equivalent to the realization of
$(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ as a simple polygon.

###### Theorem 4.1

In any realization of the internal-external visibility graph
$(\mathcal{G}_{i}nt,\mathcal{G}_{e}xt,\mathcal{P})$, the lower and upper
chains of each channel $C$ are convex.

###### Proof

For the sake of a contradiction, assume that there is a channel $C$ in the
realization of $(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ that is not
a convex polygon. Except for the vertices of the cut edges, any pair of
adjacent vertices to a vertex on $C$ are visible from each other in
$\mathcal{G}_{int}$. Therefore, the internal visibility graph
$\mathcal{G}_{int}$ forces that such a concavity on the boundary of $C$ must
happen on some vertices of the cut edges that cross this channel. Without loss
of generality, assume that such a concavity happens on the boundary of $C$ in
Fig. 6, when we connect $O_{1}$ to $O_{2}$. The vertices $A_{1}$ and $O_{2}$
are invisible pairs in $\mathcal{G}_{ext}$. According to Observation 2.1.2,
they have at least one and at most two blocking vertices, one on the clockwise
and the other on the counter-clockwise walks from $A_{1}$ to $O_{2}$. The
vertex $O_{1}$ is such a blocking vertex on the counter-clockwise walk from
$A_{1}$ to $O_{2}$. On the other hand, the last visible vertex from $A_{1}$ in
$\mathcal{G}_{ext}$ along the clockwise walk on $\mathcal{P}$ toward $O_{2}$
is a vertex like $B_{2}$ and the last visible vertex from $O_{2}$ in
$\mathcal{G}_{ext}$ along the counter-clockwise walk on $\mathcal{P}$ toward
$A_{1}$ is another vertex like $B_{1}$ which is further than $B_{2}$ from
$O_{2}$. Note that $O_{1}$ and $O_{2}$ lie on the boundary of a hole before
cutting and we have added extra vertices on all boundary segments of this
hole. The vertices $A_{1}$, $B_{1}$ and $B_{2}$ are such extra and distinct
vertices. Then, according to Observation 2 the invisible pair $(A_{1},O_{2})$
does not have a blocking vertex in the clockwise walk from $A_{1}$ to $O_{2}$.
Therefore, in any realization of
$(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$, $O_{1}$ is the only
blocking vertex of $A_{1}$ and $O_{2}$ which means that $O_{1}$ lies above the
segment $A_{1}O_{2}$ and vertex $O_{1}$ is a convex vertex on the boundary of
$C$. The same argument implies that $O_{2}$ is also a convex vertex on the
boundary of $C$, which contradicts our assumption that $C$ is concave on
$O_{1}$ or $O_{2}$.

Figure 6: Upper and lower chains of a pseudo line and their blocking vertices

The above theorem implies that in any realization of
$(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$, all channels are convex
polygons. Therefore, by the same argument as Theorem 3.1,
$(\mathcal{L},\mathcal{S})$ is stretchable if and only if
$(\mathcal{G}_{int},\mathcal{G}_{ext},\mathcal{P})$ is recognizable. On the
other hand, this reduction can be done in polynomial time and implies the
$\exists\mathbb{R}-Hardness$ of recognizing internal-external visibility
graphs of a simple polygon. It is easy to show that recognizing internal-
external visibility graphs of a simple polygon belongs to $\exists\mathbb{R}$,
and we obtain the following theorem.

###### Theorem 4.2

Recognizing internal-external visibility graphs of a simple polygon is
$\exists\mathbb{R}-Complete$.

## References

  * [1] James Abello and Krishna Kumar.  Visibility graphs and oriented matroids.  In International Symposium on Graph Drawing, volume LNCS 894, pages 147–158. Springer, 1994.
  * [2] James Abello and Krishna Kumar.  Visibility graphs of 2-spiral polygons.  LATIN’95: Theoretical Informatics, LNCS 911:1–15, 1995.
  * [3] James Abello, Hua Lin, and Sekhar Pisupati.  On visibility graphs of simple polygons.  Congressus Numerantium, pages 119–119, 1992.
  * [4] Calin Belta, Volkan Isler, and George J Pappas.  Discrete abstractions for robot motion planning and control in polygonal environments.  IEEE Transactions on Robotics, 21(5):864–874, 2005.
  * [5] Lenore Blum, Mike Shub, and Steve Smale.  On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines.  Bulletin of the American Mathematical Society, 21(1):1–46, 1989\.
  * [6] John Canny.  Some algebraic and geometric computations in pspace.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 460–467. ACM, 1988.
  * [7] Jean Cardinal and Udo Hoffmann.  Recognition and complexity of point visibility graphs.  Discrete & Computational Geometry, 57(1):164–178, 2017.
  * [8] Paul Colley, Anna Lubiw, and Jeremy Spinrad.  Visibility graphs of towers.  Computational Geometry, 7(3):161–172, 1997.
  * [9] Hazel Everett.  Visibility graph recognition - phd thesis.  1990\.
  * [10] Hazel Everett and Derek G. Corneil.  Recognizing visibility graphs of spiral polygons.  Journal of Algorithms, 11(1):1–26, 1990.
  * [11] Subir K. Ghosh.  On recognizing and characterizing visibility graphs of simple polygons.  In Scandinavian Workshop on Algorithm Theory, volume LNCS 318, pages 96–104. Springer, 1988.
  * [12] Subir K. Ghosh.  On recognizing and characterizing visibility graphs of simple polygons.  Discrete & Computational Geometry, 17(2):143–162, 1997.
  * [13] Subir K. Ghosh.  Visibility algorithms in the plane.  Cambridge University Press, 2007.
  * [14] Jacob E Goodman and Richard Pollack.  Allowable sequences and order types in discrete and computational geometry.  In New trends in discrete and computational geometry, pages 103–134. Springer, 1993.
  * [15] Jürgen Richter-Gebert.  Mnëv’s universality theorem revisited.  Séminaire Lotaringien de Combinatorie, 1995.
  * [16] Peter Shor.  Stretchability of pseudolines is np-hard.  Applied Geometry and Discrete Mathematics-The Victor Klee Festschrift, 1991.
  * [17] Ileana Streinu.  Non-stretchable pseudo-visibility graphs.  Computational Geometry, 31(3):195–206, 2005.
  * [18] Seth Teller and Pat Hanrahan.  Global visibility algorithms for illumination computations.  In Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pages 239–246. ACM, 1993.

## Appendixes

##  Appendix 0.A A Remark on BlockingVertexAssignment

In this section, we discuss the BlockingVertexAssignment and the question that
whether having a BlockingVertexAssignment as a part of the input helps to
solve the visibility graph recognition easier. Recall that,
BlockingVertexAssignment of a visibility graph of a polygon is a function
$\beta:V^{2}\rightarrow V$ that assigns a vertex to each invisible ordered
pair of vertices. This function introduced by Abello, et al., in 1994 [1] and
indicates that which vertex has first blocked the visibility of an ordered
pair of vertices. This blocking vertex is visible to the first vertex in the
ordered invisible pair and it is clear that every invisible pair must have
such a blocking vertex. There is another way to define a blocking vertex of an
invisible ordered pair: it is the first vertex in the shortest euclidean path
inside the polygon from the first to the second vertex of an invisible ordered
pair. Such a path is unique inside a simple polygon, but, there can be more
than one such paths between a pair of vertices of a polygon with holes.
Moreover, two vertices on the boundary of a simple polygon can have two
different shortest paths that lie outside the polygon. Therefore,
BlockingVertexAssignment is not well-defined for visibility graph of a polygon
with holes and for external visibility graph of a simple polygon. Abello et
al., showed that a BlockingVertexAssignment must have four conditions, which
are necessary conditions for a visibility graph to be recognizable. Later in
1997, Ghosh showed that these conditions are strictly stronger than Ghosh’s
first three necessary conditions, but, strictly weaker than Ghosh’s four
necessary conditions [12]. In 1995, Abello et al. introduced an algorithm that
recognizes the visibility graph of 2-spiral polygons from its visibility graph
and BlockingVertexAssignment in polynomial time [2]. This result opened a
question that whether having this function (BlockingVertexAssignment) as a
part of the input makes computational complexity of recognizing visibility
graphs of polygons easier? We show that recognizing internal-external
visibility graphs is still $\exists\mathbb{R}-Complete$, when we have the
BlockingVertexAssignment as a part of the input.

###### Theorem 0.A.1

BlockingVertexAssignment for the internal-external visibility graph of a
polygon, constructed from PseudoLineArrangement problem, is unique and
computable in polynomial time.

###### Proof

Consider an invisible ordered pair $(a,b)$ and the blocking vertex function
$\mathcal{B}$ for this polygon, where $a$ belongs to a channel $\mathcal{C}$.
Similar to any invisible ordered pair, there are two candidates for
$\mathcal{B}(a,b)$: last visible vertex in clockwise (name it $w$) and
counter-clockwise (name it $c$) in a walk from $a$ toward $b$ on the external
cycle. Both $c$ and $w$ are visible to $a$. Ghosh shows that these two
blocking vertex candidates see each other [12]. Therefore, $a$, $c$ and $w$
see each other and belong to the channel $\mathcal{C}$.

On the other hand, $c$ and $w$ do not belong to the same common vertices of
$Int(\mathcal{C},\mathcal{C}_{j})$. For any pair of channels
$(\mathcal{C}_{i},\mathcal{C}_{j})$, all vertices of
$Int(\mathcal{C}_{i},\mathcal{C}_{j})$ are visible from previous and next
vertices adjacent to the other three vertices in
$Int(\mathcal{C}_{i},\mathcal{C}_{j})$. Therefore, by using Observation 2, if
more than one of these three vertices belong to clockwise (resp. counter-
clockwise) walk from $a$ toward $b$, $(a,b)$ has no blocking vertex in
clockwise (resp. counter-clockwise) walk from $a$ toward $b$.

Lets denote the three vertices which are in the same intersection set with $c$
by $o_{1}$, $o_{2}$ and $o_{3}$ and those which are in the same intersection
set with $w$ by $o^{\prime}_{1}$, $o^{\prime}_{2}$ and $o^{\prime}_{3}$. If
both $c$ and $w$ are blocking vertices, $o_{1}$, $o_{2}$ and $o_{3}$ belong to
the clockwise walk from $a$ towards $b$ and in this walk we must meet them
before $w$. Similarly, we must meet $o^{\prime}_{1}$, $o^{\prime}_{2}$ and
$o^{\prime}_{3}$ before $c$ in the counter-clockwise walk from $a$ toward $b$.
Hence, vertices $a$, $b$, $c$ and $w$ have an arrangement similar to the
arrangement shown in Fig. 7. As shown in this figure, we can not cross the
convex area sorrounded by vertices of the channel $\mathcal{C}$ which are
visible from $a$ (like the area sorrounded by dotted orange, blue and green
curves in Fig. 7). In all arrangements of these points some of the adjacent
vertices of at least one of these eight intersection points, will be trapped
between the orange curve, the clockwise walk from $w$ toward $b$ and the
counter-clockwise walk from $c$ toward $b$ (see $x$ and $y$ in Fig. 7).
Therefore, we cannot meet these vertices before $w$ or $c$ in a clockwise or
counter-clockwise walk from $a$ toward $b$ without crossing the convex area
stated before. Consequently, we cannot have more than one visible blocking
vertex from $a$ for the ordered invisible pair $(a,b)$. So, the
BlockingVertexAssignment for this kind of internal-external visibility graphs
is unique.

Figure 7: Determine BlockingVertexAssignment. Blue dotted lines correspond to
some parts of counter-clockwise traverse from $a$ toward $c$ and the green
dotted lines correspond to some parts of clockwise traverse from $a$ toward
$w$. The blue dashed curve correspond to the counter-clockwise curve from $c$
toward $b$ and the green dashed curve correspond to the clockwise curve from
$w$ toward $b$. Orange curve correspond to the convex area visible from $a$.

On the other hand, we only use the first two Ghosh’s necessary conditions to
find blocking vertices and these conditions can be verified in polynomial time
[12]. So we can compute the BlockingVertexAssignment for this kind of polygon
in polynomial time.

This theorem along with Theorem 4.2 imply that, if we have both internal and
external visibility graphs of a simple polygon and its
BlockingVertexAssignment as a part of input, the recognition problem is still
$\exists\mathbb{R}-Complete$.

###### Theorem 0.A.2

Having the BlockingVertexAssignment for the internal visibility graph does not
reduce the complexity class of recognizing internal-external visibility graphs
of a simple polygon.

##  Appendix 0.B Reconstruction algorithm to reconstruct PseudoLineArrangement

Algorithm 1 Recognizing and Reconstruction algorithm for PseudoLineArrangement

##  Appendix 0.C Conclusion

In this paper, we showed that the visibility graph recognition problem is
$\exists\mathbb{R}-Complete$ for polygons with holes. Moreover, we showed that
having both internal and external visibility graphs of a simple polygon, it is
$\exists\mathbb{R}-Complete$ to recognize them as the visibility graphs of a
simple polygon. Even, having the BlockingVertexAssignment of the internal
visibility graph as a part of input, does not reduce the complexity class of
this problem. This result motivates us to guess that having
BlockingVertexAssignment for a visibility graph as a part of input will not
help us to decrease computational complexity of realizing the visibility
graphs of simple polygons. However, it is still open to determine the
complexity class of the visibility graph recognition for a simple polygon.
Although, having the external visibility graph and the
BlockingVertexAssignment of internal visibility graph apply more constraints
on reconstructing a simple polygon of a given visibility graph, but it may
limit the possible choices of the realization. Therefore, our conjecture is
that the visibility graph recognition problem for a simple polygon is still
$\exists\mathbb{R}-Complete$.