Point visibility graph recognition is NP-hard \thanks { A part of the work was done when the author visited Carleton University under DFAIT Commonwealth Scholarship of the Government of Canada.
Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility graph if and only if the 3-SAT formula is satisfiable. This reduction establishes that the problem of recognition of point visibility graphs is NP-hard.
final_draft2.tex
\documentclass[a4paper,10pt]{article}
%\usepackage[utf8x]{inputenc}
\usepackage{amsthm}
\newtheorem{lemma}{Lemma}
\newtheorem{defn}{Definition}
\newtheorem{cor}{Corollary}
\newtheorem{theorem}{Theorem}
\usepackage{graphicx}
\usepackage{graphicx,amssymb}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{epsfig, color, graphicx}
\usepackage{enumerate}
%\usepackage{rotating}
\usepackage[margin=1.0in]{geometry}
\usepackage{amssymb}
\newcommand{\IR}{\mathbb{R}}
%opening
\title{Point visibility graph recognition is NP-hard 
\thanks  
{ A part of the work was done when the author visited Carleton University under
DFAIT Commonwealth Scholarship of the Government of Canada. 
}
}
\author{
}
\begin{document}

\date{\vspace{-5ex}}
\maketitle

\begin{center}
 \mbox{\begin{minipage} [b] {3in}
 
\centerline{Bodhayan Roy}
\vspace{5mm}
\centerline{ School of Technology and Computer Science}
\centerline{ Tata Institute of Fundamental Research}
\centerline{Mumbai 400005, India}
\centerline{bodhayan@tifr.res.in}
\end{minipage}}
\end{center}
\begin{abstract}
Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility
graph if and only if the 3-SAT formula is satisfiable.
This reduction establishes that the problem of recognition of point visibility graphs is NP-hard.
\end{abstract}
\section {Introduction}
 The visibility graph is a fundamental structure studied in the field of computational geometry  
and geometric graph theory \cite{bcko-cgaa-08, g-vap-07}. 
 Some of the early applications of visibility graphs included computing 
Euclidean shortest paths in the presence of obstacles \cite{lw-apcf-79} and decomposing 
two-dimensional shapes into clusters \cite{sh-ddsg-79}. 
Here, we consider problems from visibility graph theory.
$\\$  $\\$
Let $P=\{ p_1, p_2, ..., p_n \}$ be a set of $n$ points in the plane. 
We say that two points $p_i$ and $p_j$ of $P$ 
are \emph{visible} to each other if the line 
segment $p_ip_j$ does not contain any other point of $P$. In other words,
$p_i$  and $p_j$ are visible to each other if $P \cap  {p_ip_j}=\{p_i, p_j\}$. If two points are not visible, 
they are called  \emph{ invisible } to each other.  
If a point $p_k \in P$ lies on the segment $p_ip_j$ connecting two points $p_i$ and $p_j$ in $P$, 
we say that $p_k$ blocks the visibility between $p_i$ and $p_j$, and
$p_k$ is called a \emph{ blocker} in $P$.  
$\\$ $\\$
The 
% \emph{ visibility graph} 
% (also called the 
\emph{ point visibility graph} (denoted as PVG)
 of $P$ is defined 
by associating a vertex $v_i$ with each point $p_i$ of $P$ 
and
% such that $(v_i, v_j)$ is 
an undirected edge 
$(v_i, v_j)$
of the PVG if  $p_i$ and $p_j$
are visible to each other. Observe that if no three points of 
$P$ are collinear, then the PVG is a complete graph as
each pair of points in $P$ is visible since there is no blocker in $P$. 
Point visibility graphs have been studied in the context of connectivity \cite{viscon-wood-2012},
chromatic number and clique number \cite{kpw-ocnv-2005, p-vgps-2008}.
For review and open problems on point visibility graphs, see 
% Some notable results on point visibility graphs have been summarized by 
Ghosh and Goswami \cite{prob-ghosh}.
$\\ \\$
% 
Given a point set $P$, the PVG of $P$ can be computed in polynomial time. Using the result of
 Chazelle et al. \cite{cgl-pgd-85} or Edelsbrunner et al. 
\cite{Edelsbrunner:1986:CAL},  this can be achieved in $O(n^2)$  
time.
% $\\ \\$
% \cite{viscon-wood-2012}
% It was shown by Pfender \cite{p-vgps-2008} that for every graph $G$, there is a set of points $S$ on the Euclidean plane,
% such that the subgraph induced by $S$ in the graph with vertex set $S \cup \mathbb{Z} ^2$ is $G$.
% Hence it was proved that there are PVGs of arbitrarily high chromatic number but with clique number only six.
% $\\ \\$ 
Consider the opposite problem:  given a graph $G$, determine if there is a set of points $P$ 
whose point visibility graph is $G$. This problem is called the point visibility graph 
\emph{recognition} problem \cite{prob-ghosh}.
Identifying the set of properties satisfied by all visibility graphs is called the 
point visibility graph \emph{characterization} problem.
The problem of 
actually drawing one such set of points $P$ whose point visibility graph is the given graph $G$, 
is called the point visibility graph \emph{reconstruction} problem. Such a point set itself is called a 
\emph{visibility embedding} of $G$.
$\\ \\$
Ghosh and Roy \cite{recogpvg-2014}
presented a complete characterization for 
planar point visibility graphs,
 which leads to a linear time recognition and reconstruction algorithm.
For recognizing arbitrary point visibility graphs, they 
presented three necessary conditions, and 
gave a polynomial time algorithm for testing the first necessary condition.
However, it is not clear whether the other two necessary conditions can be checked in polynomial time.
% Note that
If a 
set of necessary and sufficient conditions for recognizing point visibility graphs can be found such that they can be tested 
% complete characterization of PVGs is checkable
in polynomial time, then the recognition problem
lies in P. 
% and cannot be NP-hard unless $P=NP$.
So, it is necessary to investigate the complexity issues of recognizing point visibility graphs.
% $\\ \\$
This problem is known to be in PSPACE,
which is the only upper bound known on the complexity of the problem \cite{recogpvg-2014, prob-ghosh}. On the other
hand, problems of minimum vertex cover, maximum independent set, and maximum
clique of point visibility graphs are shown to be NP hard \cite{recogpvg-2014, prob-ghosh}.
% 
% 
% 
% 
% point visibility graphs, and
% % and conjecture that they are sufficient. 
% showed that the recognition problem lies in PSPACE.
% % We state new properties of point visibility graphs along with some known properties that are important
% % in understanding point visibility graphs.
% For planar point visibility graphs, a 
% complete characterization has been presented which leads to a linear time recognition and reconstruction algorithm  \cite{recogpvg-2014}. 
$\\ \\$
In this paper,
we show that the recognition problem for $PVGs$ is NP-hard.
In Sections \ref{secsgg} and \ref{secmsgg}, we develop a \emph{slanted grid graph} that has a unique visibility embedding.
In Section \ref{sec3sat}, 
we  
reduce the 3-SAT problem to the recognition problem
for point visibility graphs using the grid 
graph.
% developed in Sections \ref{secsgg}
% and \ref{secmsgg}. 
In Section \ref{conclrem}, we conclude the paper with a few remarks.

\section{Slanted grid graphs} \label{secsgg}
In this section, we define 
% and study the
a special type of $PVG$ called the
\emph{slanted grid graph} ($SGG$). Intuitively, an $SGG$ is a $PVG$
resembling a grid graph \cite{diestel} with two extra vertices so that in its visibility embedding, every line passes through
at least one of these two vertices. These two extra vertices are called \emph{vertices of convergence}.
% \begin{defn}
% % [Point Visibility Graph and Visibility Embedding]
% Let $P$ be a set of points and $G=(V,E)$ be a graph defined as follows.
% To each point $p_i \in P$,
% we associate a vertex $v_i \in V$.
% There is an edge $(v_i,v_j)\in E$ if and only if $P \cap p_ip_j = \{p_i,p_j\}$.
% The graph $G$ is called the \emph{point visibility graph} (PVG) of $P$.
$\\ \\ $
Let $G=(V,E)$ be 
the $PVG$ of a point set $P$.
% a PVG, $P$ be a set of points
Let $f:V \longrightarrow P$ be a bijection.
We say that the pair $\langle P,f \rangle$ is a \emph{visibility embedding} of $G$
if
$$P \cap p_ip_j = \{p_i,p_j\} \Longleftrightarrow (f^{-1}(p_i),f^{-1}(p_j))\in E \enspace.$$
% \end{defn}
 % \begin{defn}
Let $G=(V,E)$ be a PVG, and 
$\xi=\langle\{p_1,p_2,...,p_n\}, f\rangle$ and $\xi'=\langle\{p_1',p_2',...,p_n'\}, f'\rangle$ be two visibility embeddings of $G$.
Let $L$ be a line in $\xi$
and let $\langle p_{i_1}, p_{i_2},...,p_{i_{\ell}}\rangle$
be the sequence of all points in $\xi$ that lie on $L$ in this order.
We say that $L$ is \emph{preserved} in $\xi'$
if all the points in the sequence $L'=\langle f'(f^{-1}(p_{i_1})), f'(f^{-1}(p_{i_2})),...,f'(f^{-1}(p_{i_{\ell}}))\rangle$
lie on the same line, in the same order and no other point of $\xi'$ lies on $L'$.
% \end{defn}
% \begin {defn}
%   A line in a visibility embedding $\xi$ of a point visibility graph $G$ is said to be \emph{preserved} in 
% another embedding $\xi '$ of $G$ if all of its vertices remain collinear in the same order in $\xi '$, and no other vertex
% is collinear with them.
% 
% \end {defn}
 
%\begin {defn}
 %A PVG that has got only a  unique embedding upto preservation of all lines is called a 
%\emph{single  embedding   graph}.
%\end {defn}
$ \\ $
Let $m\in \mathbb{N}$ and $n\in \mathbb{N}$ be two numbers such that $m \neq 0$ and $n\neq 0$.
Consider the graph $G = (V,E)$, where $V$ and $E$
are defined as follows.
\begin{eqnarray*}
V &=& \{v_{i,j} \vert 1\leq i \leq n \textrm{ and }1\leq j \leq m\} \cup \{v_1,v_2\}\\
E &=& \{(v_{i,j},v_{k,l}) \vert i\neq k \textrm{ and } j\neq l\} 
\cup \{(v_1,v_{1,j})\vert 1\leq j\leq m\} \cup \{(v_2,v_{i,1})\vert 1\leq i\leq n\}\cup\{(v_1,v_2)\}\\
 &\cup&  \{(v_{i,j},v_{i+1,j}) \vert 1 \leq i \leq n-1 \textrm{ and }  \vert 1 \leq j \leq m  \} 
 \cup \{(v_{i,j},v_{i,j+1}) \vert 1 \leq i \leq n  \textrm{ and }  \vert 1 \leq j \leq m-1  \} 
\end{eqnarray*}
We call this graph a \emph{slanted grid graph} (SGG),
which is a $PVG$.
% We can see that any SGG is a PVG.
% Indeed,
Consider a set of points 
$$P = \{p_{i,j} \vert 1\leq i \leq n \textrm{ and }1\leq j \leq m\} \cup \{p_1,p_2\}$$
and associate $v_1$ to $p_1$, $v_2$ to $p_2$ and $v_{i,j}$ to $p_{i,j}$ for $1\leq i\leq n$ and $1\leq j\leq m$.
Choose the coordinates of the points in $P$
in such a way that the non-ordinary lines in $P$ consist of
$\langle p_1,p_{1,j},p_{2,j},...,p_ {n,j}\rangle$ for $1\leq j\leq m$
and $\langle p_2,p_{i,1},p_{i,2},...,p_ {i,m}\rangle$ for $1\leq i\leq n$
(Figure \ref{sgg}).
Then $P$ is a visibility embedding of $G$, and points of $P$ are referred to as \emph{embedding points}.

 $ \\ $
In 
% Lemma \ref{lem1},
the following lemma,
we prove that this visibility embedding is actually unique,
up to the preservation of the lines.
\begin{figure}[h]\label{sgg}
\begin{center}
\centerline{\hbox{\psfig{figure=a28_f.pdf,width=0.700\hsize}}}
\caption{Visibility embedding of a slanted grid graph }
\label{sgg}
\end{center}
\end{figure}
\begin {lemma} \label{lem1}
%  The embedding of $G$ depicted in Figure \ref{sgg} is the only possible embedding of $G$, unique up to the preservation of lines.
$G$ has a unique visibility embedding, up to the preservation of lines (Figure \ref{sgg}).
\end {lemma}
\begin{proof} There are $m+1$ and $n+1$ vertices in $G$ adjacent to $v_1$ and $v_2$  respectively. 
So there are $m+1$ and $n+1$ rays originating from $p_1$ and $p_2$ in a visibility embedding of $G$ respectively.
% The point $p_2$ lies on one of the $m+1$ rays from $p_1$. 
We leave aside the two rays from  $p_1$ and $p_2$ 
which account  for the edge between them. There are exactly $m \times n$ intersection points formed by the remaining rays. 
% where 
% and 
% Points corresponding to the vertices of $G$
Observe that embedding points  
can only be placed on these $m \times n$ intersection points.
% the $m \times n$ points corresponding to the remaining vertices of $G$ can be placed only at these intersection points. 
We call this configuration a \emph{slanted grid}. Wlog we assume that $p_1$ is placed
to the right of all other points, and $p_2$ is placed above all the other points (see Figure \ref{sgg}).
For convenience, we refer to the rays from $p_1$ as \emph{horizontal} and the rays from $p_2$ 
as \emph{vertical}.
Hence, the embedding points can only permute their positions
on the intersection points of rays.
% , although they are actually slanted. 
% Note that they are slanted since they converge to $p_1$ or $p_2$.

$ \\$
% Hence the vertices can only permute their positions.
Since $\{v_{1,1}, v_{2,1}, \ldots, v_{n,1} \}$ are adjacent to $v_2$, 
the embedding points $\{p_{1,1}, p_{2,1}, \ldots, p_{n,1} \}$ must occur on the topmost horizontal ray from $p_1$.
Since $v_{1,1}$ is adjacent to $v_1$, $p_{1,1}$ must be embedded to the left of $p_1$ with no other embedding point 
on $p_{1,1}p_1$. For $1 \leq i \leq n-1$,  $v_{i+1,1}$ is adjacent to $v_{i,1}$, and therefore,
$p_{i+1,1}$ must be embedded to the left of $p_{i,1}$ with no other embedding point 
on $p_{i+1,1}p_{i,1}$. Hence, the topmost horizontal line is preserved.
Since the vertices $\{v_{1,2}, v_{2,2}, \ldots, v_{n,2} \}$ are the only vertices
adjacent to  $\{v_{1,1}, v_{2,1}, \ldots, v_{n,1} \}$,
  $\{p_{1,2}, p_{2,2}, \ldots, p_{n,2} \}$ must occur on the second-topmost horizontal ray from $p_1$.
By applying the previous reasoning, the second-topmost horizontal line is also preserved.
% Similarly, it can be shown that all the horizontal and hence vertical lines are preserved.
Similar arguments hold for other horizontal and vertical rays.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% SECTION 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 \begin{figure}[h] 
\begin{center} 
\centerline{\hbox{\psfig{figure=a29_f.pdf,width=0.700\hsize}}}
\caption{An embedding of the $SGG$ after deletion of vertices.}
\label{dsgg}
\end{center}
\end{figure}
\begin{figure}[h] 
\begin{center} 
\centerline{\hbox{\psfig{figure=a30_f.pdf,width=0.700\hsize}}}
\caption{Visibility embedding of a modified slanted grid graph. $G'$ is not a part of the MSGG.  }
\label{msgg}
\end{center}
\end{figure}
\section{Modified slanted grid graphs} \label{secmsgg}
In a visibility embedding of an $SGG$, every intersection point contains an embedding point. However,
if we delete some embedding points, then it is not clear whether the visibility graph of the remaining point set 
has a unique visibility embedding.
In order to have a unique embedding after deletion, some new vertices are added to $G$ which facilitate 
a unique visibility embedding of $G$.
\subsection{Construction of a modified slanted grid graph } \label{consmsgg}
 Consider the unique embedding $ \xi$ of a slanted grid graph  $G$ with $n \times n$ embedding points
 and the two embedding points of convergence.
 We construct a modified slanted grid graph (denoted as $MSGG$) 
 by adding some vertices to $G$ and then deleting some other vertices from it.
 We now describe the modification of $G$. Let $G$ be the $SGG$ on $(n \times n) + 2$ vertices defined in the previous section.
 Let $m = \lfloor \frac{\sqrt{n}}{2} \rfloor$.
 Note that the removal of vertices from $V$ also implies the removal of their incident edges from $E$.
 We make the following modifications in $G$.
 \begin{eqnarray*}
V &=& (V \setminus \{ v_{i,j} \vert   n-m+1 \leq i \leq n      3\leq j \leq n      \} )  
\cup \{v_{i,j} \vert n+1 \leq i \leq 2n^4-n \textrm{ and } 1\leq j \leq 2\}  \\
& &  \cup \{v_{i,j} \vert 1\leq i \leq 2 \textrm{ and } n+1 \leq j \leq 25n^8\}                 \\
% 
% 
% 
E &=& E \cup \{ (v_{i,j},v_{i-1,j}) \vert   2n^4-n \leq i \leq 2n^4 \textrm{ and } 1 \leq j \leq 2 \}\\
& & \cup \{  (v_{i,1}, v_{j,2}) \vert  1 \leq i, j \leq 2n^4       \} \\
& & \cup \{  (v_{i,j}, v_{k,l}) \vert 2n^4-n \leq i \leq 2n^4 \textrm{ and } 1 \leq j \leq 2 
\textrm{ and }  1 \leq k \leq n-m+1          \textrm{ and }         3 \leq l \leq n           \} \\ 
& & \cup \{ (v_{i,j-1},v_{i,j}) \vert   1 \leq i \leq 2  \textrm{ and } 25n^8-n \leq i \leq 25n^8 \} \\
& & \cup \{  (v_{1,i}, v_{2,j}) \vert  1 \leq i, j \leq 25n^8       \} \\
& & \cup \{  (v_{i,j}, v_{k,l}) \vert  1 \leq i \leq 2 \textrm{ and }  25n^8-n \leq j \textrm{ and }  \leq 25n^8 
\textrm{ and }  1 \leq k \leq n-m+1          \textrm{ and }         3 \leq l \leq n           \} \\ 
& & \cup \{  (v_{i,j}, v_{k,l}) \vert  1 \leq i,k \leq 2 \textrm{ and }  3 \leq j \textrm{ and }  \leq 25n^8 
\textrm{ and }    3 \leq l \leq 2n^4           \} \\ 
% \\ 
% \\ \\
% & & \{(v_{i,j},v_{k,l}) \vert i\neq k \textrm{ and } j\neq l\} 
% \cup \{(v_1,v_{1,j})\vert 1\leq j\leq m\} \cup \{(v_2,v_{i,1})\vert 1\leq i\leq n\}\cup\{(v_1,v_2)\}\\
%  & & \cup  \{(v_{i,j},v_{i+1,j}) \vert 1 \leq i \leq n-1 \textrm{ and }  \vert 1 \leq j \leq m  \} 
%  \cup \{(v_{i,j},v_{i,j+1}) \vert 1 \leq i \leq n  \textrm{ and }  \vert 1 \leq j \leq m-1  \} 
\end{eqnarray*}
%  The modified $G$ still has a unique embedding. 
Now we construct a visibility embedding of the modified $G$, from the initial unique visibility
embedding of $G$ in Figure \ref{sgg}.
 Let $L_1$ and $L_2$ be the rightmost and second-rightmost lines of the visibility-embedding of an $MSGG$ (Figure \ref{msgg}).
 Let $L_3$ and $L_4$ be the topmost and second-topmost lines of the visibility-embedding of an $MSGG$.
 The
 bottommost horizontal line and leftmost vertical line are labelled $L_5$ and $L_6$, respectively.
As shown in Figure \ref{msgg}, the two points of convergence are above and to the 
right of the embedding. As before, $p_{i,j}$ is the embedding point corresponding to the vertex $v_{i,j}$.
% 
% $ \\$
% We use the following method to construct an $MSGG$ from a given $SGG$. In the construction, the positions of the vertices of $G$
% actually refer to the position of their corresponding points in the embedding in Figure \ref{sgg}.
% 
\begin{enumerate}
% \item Let $m$ be any integer such that $0 \leq m \leq \frac{\sqrt{n}}{2}$.
 
\item \label{secstep} Delete the $(n-2) \times m$ bottom-left subgrid of $G$ (See Figure \ref{dsgg}).
 At a later stage, we embed a graph $G'$ in the space thus created.
\item \label{thrstep} To the left of $L_6$, place $2n^4$ embedding points on $L_4$, and 
% To the left of $L_6$, place
 $2n^4$ embedding points on $L_3$ (See Figure \ref{msgg}).
These embedding points must be placed in such a way that 
$(a)$ each embedding point added to $L_3$ blocks an embedding point on $L_4$ from $p_2$,
% The added vertices of $L_3$ see every embedding point of $G$ not on $L_3$.
% The added vertices of $L_4$ see every embedding point of $G$ not on $L_4$, and not $p_2$.
$(b)$ each embedding point added on $L_3$ sees every embedding point of $G$ not on $L_3$, and
$(c)$ each embedding point added on $L_4$ sees every embedding point of $G$ not on $L_4$.
To achieve this, the embedding points on $L_4$ and $L_3$ 
are added by considering the intersections of $L_3$ and $L_4$ with lines containing the edges of $G$.
Such intersections are at most twice the number of edges in $G$. Each new embedding point can be placed on $L_4$ and its 
blocker on $L_3$ by avoiding these intersections.
  Add all edges between embedding points that are visible to each other.

\item Below $L_5$, place $25n^8$ embedding points on $L_2$, and
% 
% \item Below $L_5$, place 
$25n^8$ embedding points on $L_1$ (See Figure \ref{msgg}).
These embedding points must be placed in such a way that $(a)$ each embedding point added to $L_1$ blocks
an embedding point on $L_2$ from $p_1$,
$(b)$ each embedding point added on $L_1$ sees every embedding point of $G$ not on $L_1$, and
$(c)$ each embedding point added on $L_2$ sees every embedding point of $G$ not on $L_2$.
To achieve this, the embedding points are added by following the method in step \ref{thrstep}.
% 
% The added vertices of $L_1$ see every vertex of $G$ not on $L_1$.
% The added vertices of $L_2$ see every vertex of $G$ not on $L_2$, and not $p_1$.
 Add all edges between embedding points that are visible to each other.
% Add edges appropriately.
%  
% \item \label{lastep} Choose any integer $q$ such that $0 \leq q \leq m$.
% Consider the vertical lines from which the points of the  $m \times m$ bottom-left subgrid have been deleted.
% Select any $q$ of these vertical lines, and delete all but the top two points from each of them.
% When deleting a vertex $v_i$ that blocks vertices $v_j$ and $v_k$, draw the edge $(v_j,v_k)$. 
\end{enumerate}
Henceforth $G$ is referred to as the \emph{modified slanting grid graph}, denoted as $MSGG$.
Observe that 
 for all pairs of embedding points $p_{i,j}$ and $p_{k,l}$ where $i \neq k$ and $j \neq l$,
$p_{i,j}$ and $p_{k,l}$ are mutually visible.
% each embedding point sees all embedding points not on the same horizontal or vertical lines.
% $ \\ $
% At a later stage, we will embed a graph in the space created by 
% step \ref{secstep}. 


%  $ \\ $
% Now we call this new graph  a \emph{ modified   slanted   grid  graph}  $ (MSGG)$ derived from $G$. 
% Note that the property of each vertex being adjacent to all the other
% vertices outside of its own horizontal and vertical lines, is preserved. Overall, we have extended $L_1$,
% $L_2$, $L_3$ and $L_4$, removed the vertices (except on $L_3$ and $L_4$) of a few vertical lines ,
% and removed the bottom  
% left portion of the graph for another graph to be embedded in that region.
\subsection{Unique visibility embedding of MSGG}
% Here we start with properties of any point visibility graphs
% We start with a few properties, and then
Here we prove that every $MSGG$ has
only one visibility embedding, unique up to the preservation of lines.
We start with a few properties.
 \begin{figure}[h] 
\begin{center} 
\centerline{\hbox{\psfig{figure=a33_f.pdf,width=0.600\hsize}}}
\caption{(a) The point $p_i$ is on $L$ and hence sees at most $l+2$ embedding points. (a) The point
$p_i$ is not on $L$ and hence sees at least $k$ embedding points.}
\label{figsmallemma}
\end{center}
\end{figure}
\begin{lemma}\label{smallemma}
Let $H_1$ be a $PVG$ with visibility embedding $\xi$. Let $L$ be a line in  $\xi$
such that $(i)$ there are $k$ embedding points on $L$, and $(ii)$ $l$ embedding points not on $L$.
Let $v_i$ be a vertex of $H_1$ and $p_i$ its corresponding embedding point in $\xi$.
If $p_i$ lies on $L$, then $deg(v_i) \leq l+2$. Otherwise, 
% if $p_i$ does not lie on $L$ then 
$deg(v_i) \geq k$.
\end{lemma}
 \begin{proof} 
If $p_i$ lies on $L$ then $p_i$ sees at most 
two embedding points on $L$, and at most all $l$ embedding points that are not on $L$ (see Figure \ref{figsmallemma}(a)).
% all the $k$ points not on $L$, and two more points on $L$.
If $p_i$ does not lie on $L$, then all $k$ embedding points on $L$ lie on distinct lines passing through $p_i$.
So, $p_i$ sees at least $k$ embedding points (see Figure \ref{figsmallemma}(b)).
\end{proof}
\begin{lemma} \label{lp} %  lp stands for line preserve
Let $H_2$ be a $PVG$ with visibility embedding $\xi$. 
Let $L$ be a line in $\xi$ such that $(i)$ there are $k$ embedding points on $L$, and $(ii)$ $l$ embedding points not on $L$.
If $k \geq (l+3)^2$ then $L$ is preserved 
in every visibility embedding of $H_2$ (Figure \ref{fig1.5lp}(a)).
% Suppose there is a line $L$ in $\xi$ 
% with $l$ points outside of $L$ and $ k \geq (l+3)^2 $ points on $L$. Then $L$ is preserved 
% in every visibility embedding of $G$.
 %If some visibility embedding $\xi$ of a PVG $G$ has a line $L$ with $k$ vertices on the 
%ine, and $l$ vertices outside the line, then if
%$ k \geq (l+3)^2 $, the line is preserved in every visibility embedding of the PVG. 
\end{lemma}
\begin{proof} 
% Let us assume that $L$ is not preserved in some visibility embedding $\xi'$ of $G$. 
% The following cases can arise:
By the hypotheses, $H_2$ has $k+l$ vertices. Let us assume on the contrary that $L$ is not preserved in some visibility 
embedding $\xi'$ of $H_2$. Let $\phi$ denote the bijection between $\xi$ and $\xi'$, and let $\phi(L)$ be 
the image of $L$ in $\xi'$. 
We have the following cases depending on the collinearity of the embedding points of $\phi(L)$.  
$\\ \\$
\textbf{Case 1:} All embedding points in $\phi(L)$ are collinear.
$\\$
\textbf{Case 2:} All embedding points in $\phi(L)$ are not collinear.
$\\ \\$
Consider \emph{Case 1}. 
Let $L'$ be the line containing all embedding points of $\phi(L)$.
Consider the situation where $L'$ contains only the embedding points of $\phi (L)$.
 Let $p_{i-1}$, $p_i$ and $p_{i+1}$ be three consecutive embedding points on $L$
  whose corresponding vertices in $H_2$ are $v_{i-1}$, $v_i$ and $v_{i+1}$ respectively.
  Clearly,  $\phi(p_{i-1})$, $\phi(p_{i})$ and $\phi(p_{i+1})$ must be consecutive embedding points on $L'$,
  since $(v_{i-1},v_i)$ and $(v_i, v_{i+1})$ are edges of $H_2$. A similar argument holds for the first and last 
  embedding points of $L'$. Hence, $L$ is preserved.
%   $\\ \\$
  Consider the other situation where $L'$ contains an embedding point $p_i$ not in $\phi(L)$.
% Let $p_i \notin L$ be an embedding point in $\xi$, with its 
Let the corresponding vertex of $p_i$ in $H_2$ be $v_i$.
Since $\phi(p_i)$ lies on $L'$, $k \leq deg(v_i) \leq l+2$ by Lemma \ref{smallemma},
contradicting the assumption that $k \geq (l+3)^2$.
$\\ \\$
Consider \emph{Case 2}. If all embedding points of $\phi(L)$ are not collinear, then $(i)$ some
  embedding points (say, $l+3$) of $\phi(L)$ are collinear, or $(ii)$ no $(l+3)$ embedding points of $\phi(L)$ 
are collinear. 
% We have the following cases.
Consider $(i)$. Let $p_i \in \phi(L)$ and $p_i \notin L'$ such that $p_i$ is closest to $L'$ among all embedding points of 
$\phi(L)$. Since $\phi ^ {-1} (p_i)$ sees at most two points on $L$, $p_i$ does not see more than two of these $l+3$ 
points. Hence, $p_i$ requires $l+1$ blockers where no blocker is from $\phi(L)$ by the choice of $p_i$.
On the other hand, there are only $l$ points not in $\phi(L)$, a contradiction.
$\\ \\$
% 
% 
% 
% 
% \begin{enumerate}[(a)]
% \item \textbf{At least $l+3$ points of $\phi(L)$ are collinear.} Let $L'$ be the line containing these $l+3$ points of $\phi(L)$.
% Let $p$ be the point of $\phi(L)$ closest to $L'$
% and outside of it.
% The point $p$ can be adjacent to at most two points of $\phi(L)$. 
% Therefore, $p$ needs at least $l+1$ blockers to prevent it from seeing too many points of $\phi(L)$ on $L'$. 
% This is impossible, since there are only $l$ points outside of $\phi(L)$.
% 
% \item 
Consider $(ii)$. Let $p_i \in \phi(L)$. Since $\vert \phi(L) \vert \geq (l+3)^2$
by assumption and no $(l+3)$ embedding points of $\phi(L)$ are collinear, there are at least $(l+4)$ 
distinct lines passing through $p_i$. So, the degree of the corresponding vertex $v_i$ of $p_i$ in $H_2$ has degree at least $(l+4)$.
On the other hand, by Lemma \ref{smallemma}, $deg(v_i) \leq l+2$, a contradiction. 
\end{proof}
% % This leads to a contradiction. \end{proof}
% % \end{enumerate}
% % \end{enumerate}
 $\\$
Let $L_a$ and $L_b$ be two lines in a visibility embedding $\xi$ of a special type of PVG such that most of the embedding points of
$\xi$ are on $L_a$ and $L_b$ (Figure \ref{fig1.5lp}(b)). In the following lemma, 
we show that $L_a$ and $L_b$ are preserved in every visibility embedding 
of the PVG.
% 
% 
% 
% 
% In the next lemma, we prove that for a certain type of PVG with a visibility embedding having two lines with many points
% and very few points outside of those lines, the lines are preserved. For the MSGG in Figure \ref{msgg}, this implies that the lines
% $L_1$ and $L_2$ are preserved in every visibility embedding of it. 
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a35_f.pdf,height=0.400\hsize}}}
\caption{(a) The line $L$ is preserved. (b) Both lines $L_a$ and $L_b$ are preserved.}
\label{fig1.5lp}
\end{center}
\end{figure}
\begin{lemma} \label {2lp}
Let $H_3$ be a PVG with visibility embedding $\xi$. Let
% \begin{eqnarray*}
$L_a = \langle p_1,p_2,...,p_k\rangle$, and 
$L_b = \langle p_1,p_{k+1},...,p_{2k-1}\rangle$
% \end{eqnarray*}
be two lines in $\xi$ such that 
$k \geq (l+3)^2$, where $l$ denotes the number of embedding points in $\xi\setminus\{L_a\cup L_b\}$.
% 
% 
% 
% 
% 
% 
% 
% 
% 
% there are at most $l \geq 1$ embedding points 
% in $\xi\setminus\{L_a\cup L_b\}$ and $k \geq (l+3)^2$.
Let $p_{2k}$ be an embedding point satisfying the following properties.
\begin{enumerate}
\item   \label{a1.2} The embedding point $p_{2k}$ is adjacent to all embedding points in $L_b$, and is not adjacent
to any other embedding point of $\xi$.
\item \label{a1.1} For $1< i\leq k$, $p_{k+i-1}$ blocks $p_i$ from $p_{2k}$ .
\item  \label{a1.3} Every embedding point in $L_a\setminus \{p_1\}$ is adjacent to every embedding point in $L_b\setminus \{ p_1 \}$.
\item \label{a1.4}  No embedding point in $\xi \setminus (L_a \cup L_b \cup \{ p_{2k} \} )$ is adjacent to all embedding points of $L_b$.
\end{enumerate}
Then $L_a$ and $L_b$ are preserved in every visibility embedding of $H_3$, and the embedding points in 
$\xi \setminus (L_a \cup L_b \cup \{ p_{2k} \} )$ lie outside the convex hull of $(L_a \cup L_b \cup \{ p_{2k} \})$.
\end{lemma}
% \begin{lemma} \label {2lp}
%  Suppose a PVG $G$ has a visibility embedding with lines 
% $l_1 = (v_1, v_2, \ldots , v_k)$ (where $k \geq 4$) and 
% $l_2 = (v_1, v_{k+1}, \ldots , v_{2k-1})$ and a vertex $v_{2k}$ such that $v_{2i-1}$ blocks $v_i$ from $v_{2k}$ 
% for all $i$ such that $1 \leq i \leq k-1 $. If $v_{2k}$ is adjacent only to vertices of 
% $l_2$, and there are only $l$ more vertices in the 
% graph, so that $ k \geq (l+3)^2 $, then lines $l_1$ and $l_2$ are preserved.
% \end{lemma}
\begin{proof} Let $\xi'$ be any other visibility embedding of $H_3$. 
Let $\phi$ denote the bijection between $\xi$ and $\xi'$. So, $\phi(L_a)$ and $\phi(L_b)$ are  
the images of $L_a$ and $L_b$ in $\xi'$, respectively.
We know that embedding points of $\phi(L_b)$ are adjacent to $\phi(p_{2k})$.
If the orders along $\phi(L_b)$ are different from that of $L_b$, then the corresponding 
edges in the PVGs for $\xi$ and $\xi'$ are different. Hence, $\xi$ and $\xi'$ are not the visibility
embeddings of the same PVG, which is a contradiction. Consider any three consecutive points 
$\phi(p_i)$, $\phi(p_{i+1})$ and $\phi(p_{i+2})$ of $\xi'$ on $\phi(L_b)$ (Figure \ref{fig2lp}(a)).
If $\phi(p_{i+1})$ is the blocker between $\phi(p_i)$ and $\phi(p_{i+2})$, then they
are collinear. Otherwise, consider the triangle $\phi(p_i) \phi(p_{i+2}) \phi(p_{2k})$.
If $\phi(p_{i+1})$ lies inside the triangle, then some point from
$\xi' \setminus ( \phi(L_b) \cup \{ \phi(p_{2k}) \} )$ can block $\phi(p_i)$ and $\phi(p_{i+2})$.
Consider the other case where 
 $\phi(p_{i+1})$ lies outside the triangle.
 Since the blocker between 
 $\phi(p_i)$ and $\phi(p_{i+2})$ must be adjacent to $\phi(p_{2k})$, and only the points of 
 $\phi(L_b)$ are adjacent to $\phi(p_{2k})$, there cannot be any blocker of $\phi(p_i)$ and $\phi(p_{i+2})$.
%  
%  
%  
%  
%  then the blocker of
% $\phi(p_i)$ and $\phi(p_{i+2})$ cannot come from $\phi(L_b)$ but must be adjacent to $\phi(p_{2k})$,
% which is a contradiction. 
Hence, the points of $\phi(L_b)$ must either be collinear or form a 
reflex chain facing $\phi(p_{2k})$ (Figure \ref{fig2lp}(b)).
% 
% 
%  The embedding points of $\phi(L_b)$ have to form a convex chain with respect to $\phi(p_{2k})$,
% since any non-convex part of the chain would require blockers adjacent to $\phi(p_{2k})$.
$\\ \\$
Before showing that $L_b$ is preserved, we show that $L_a$ is preserved.
Since the embedding points of $\phi(L_b)$ form a reflex chain or a straight line and they are 
the only embedding points adjacent to $\phi(p_{2k})$, no embedding point of $(\phi(L_b) \cup \{ \phi(p_{2k}) \})$
can be a blocker for any pair of the remaining embedding points of $\xi'$.
In addition, these embedding points are also not blockers between $\phi(p_1)$ and any other embedding point of $\xi'$.
So, applying Lemma \ref{lp} on $(\xi' \setminus ((\phi(L_b) \setminus \{ \phi(p_1) \}) \cup \{ \phi(p_{2k}) \} ))$,
we get that $L_a$ is preserved.
$\\ \\$
Since $L_a$ is preserved and $ \vert \phi(L_a) \vert = \vert \phi(L_b) \vert$, the 
embedding points of $\phi(L_a)$ cannot be blockers for pairs of 
embedding points of $\phi(L_b)$. Since 
no embedding point $p_q \in (\xi' \setminus \{ \phi(L_a) \cup \phi(L_b) \cup \{ \phi(p_{2k}) \} \})$
can lie 
inside the region bounded by $\phi(L_a)$ and $\phi(L_b)$,
% on the line segment $\phi(p_i)\phi(p_j)$ where
% $\phi(p_i) \in \phi(L_a)$ and $\phi(p_j) \in \phi(L_b)$,  
$p_q$ cannot be a blocker for pairs of 
embedding points of $\phi(L_b)$.
Hence, the blockers for embedding points of $\phi(L_b)$ must come from $\phi(L_b)$ itself.
So, the points of $\phi(L_b)$ are collinear and $L_b$ is preserved.
\end{proof}
% 
% \noindent
% Let $G$ be a modified slanted grid graph as described in Section \ref{consmsgg}.
% 
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a36_f.pdf,height=0.400\hsize}}}
\caption{
(a) In $\xi'$, $\phi(L_b)$ is not a reflex chain. 
(b) In $\xi'$, $\phi(L_b)$ a reflex chain facing $\phi(p_{2k})$. 
}
\label{fig2lp}
\end{center}
\end{figure}
 \begin{lemma} \label{4lp}
 Let $G$ be a modified slanted grid graph with visibility embedding $\xi$ (Figure \ref{msgg}).
 Let $L_1$ and $L_2$ be the rightmost and the second-rightmost lines in $\xi$, respectively.
 Let $L_3$ and $L_4$ be the topmost and the second-topmost lines in $\xi$, respectively. 
  The lines $L_1$, $L_2$, $L_3$ and $L_4$ 
  are preserved in every visibility embedding of $G$.  
 \end{lemma}
\begin{proof} 
Let $\xi'$ be any other visibility embedding of $G$. 
Let $\phi$ denote the bijection between $\xi$ and $\xi'$. So, $\phi(L_1)$, $\phi(L_2)$, $\phi(L_3)$ and $\phi(L_4)$ are  
the images of $L_1$, $L_2$, $L_3$ and $L_4$ in $\xi'$, respectively.
$\\ \\$
First we show that $L_1$ and $L_2$ are preserved.
$\phi(L_1) \setminus \{\phi(p_2)\}$ and $\phi(L_2)\setminus \{\phi(p_2)\}$ contain $25n^8 + n $
embedding points each by construction and $\xi' \setminus (\phi(L_1) \cup \phi(L_2))$
contains at most $4n^4 + n^2 - 2n - m^2 + 1 $ embedding points by construction, where
$1 \leq \ m \leq \frac{\sqrt{n}}{2}$. Observe that $25n^8 + n + 1 \geq (4n^4 + n^2 - 2n - m^2 + 4)^2$ for large $n$. 
Since $k \geq (l+3)^2$, where $k = 25n^8 + n + 1$ and $ l = 4n^4 + n^2 - 2n - m^2 + 1$, both
$L_1$ and $L_2$ are preserved by Lemma \ref{2lp}.
% 
% the hypotheses of Lemma \ref{2lp} are satisfied.
% So, first we embed $\phi(L_1)$ and $\phi(L_2)$, which are preserved due to Lemma \ref{2lp}, where $\phi(p_1)$ 
% acts as $p_{2k}$.
$\\ \\$
Now we show that $L_3$ and $L_4$ are preserved.
Let us start by identifying the partition of blockers in $\xi'$ with respect to $\phi(L_1)$ and $\phi(L_2)$.
Without loss
of generality, let $\phi(p_2)$ be the topmost point, 
$\phi(L_1)$ be to the right of $\phi(L_2)$ and $\phi(p_1)$ be to the right of $\phi(L_1)$ in $\xi'$ (see Figure \ref{msgg}). 
% Let us identify the partition of blockers in $\xi'$ with respect to $\phi(L_1)$ and $\phi(L_2)$.
Since the adjacency relationships between  $\phi(L_1)$ and $\phi(L_2)$ cannot change, and 
% Since the edges between $\phi(L_1)$ and $\phi(L_2)$ have to be maintained and
$\phi(p_1)$ is adjacent only to the embedding points of 
$\phi(L_1)$, all embedding points of $\xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \} )$ 
must be to the left side of $\phi(L_2)$.
Hence, embedding points of $ \phi(L_1) \cup \phi(L_2) \cup \{\phi(p_1)\}$ cannot be blockers 
for any pair of embedding points in $ \xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \{\phi(p_1)\} )$.
% in between the embedding points of the rest of $G$.
% $ \\ \\ $
%  $ \\ \\ \\ \\ \\ \\ \\ \\$ 
Embedding points of $\phi(L_3)$ must form a straight line or a reflex chain facing $\phi(p_2)$
as shown in Lemma \ref{2lp}.
% Indeed, any non-reflex part of the chain would require blockers adjacent to $\phi(p_2)$,
% but $\phi(p_2)$ is adjacent only to the embedding points of $\phi(L_3)$
% and t
Therefore the
% .
% Hence, the embedding points of   $\phi(L_1) \cup \phi(L_2) \cup \phi(L_3)$ lie outside of the 
% convex hull of $\xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \phi(L_3))$ and 
embedding points of   $(\phi(L_1) \cup \phi(L_2) \cup \phi(L_3) \cup \{ \phi(p_1), \phi(p_2) \})$
 cannot be the blockers of the remaining 
embedding points of $\xi'$. 
% \setminus (\phi(L_1) \cup \phi(L_2) \cup \phi(L_3) \cup \{ \phi(p_1), \phi(p_2) \})$.
% In  $\xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \phi(L_3) \cup \{ \phi(p_1), \phi(p_2) \})$, 
Again, the set 
$\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \}) $
has $2n^4 + n - 2$ embedding points and
$\xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \phi(L_3) \cup \phi(L_4))$ has at most $(n-2)^2 - m^2$ embedding points.
% 
% 
Observe that $2n^4 + n - 2 \geq ((n-2)^2 - m^2 +3)^2$ for large $n$. 
Since $k \geq (l+3)^2$, where $k = 2n^4 + n - 2$ and $ l = ((n-2)^2 - m^2)$,
the embedding points of $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$ 
are collinear in their original order by
Lemma \ref{lp} on  $\xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \phi(L_3) \cup \{ \phi(p_1), \phi(p_2) \})$.
% 
% By elementary calculus,
% $2n^4 + n - 2 \geq ((n-2)^2 - m^2 +3)^2$ embedding points. So, applying
% Lemma \ref{lp} to  $\xi' \setminus (\phi(L_1) \cup \phi(L_2) \cup \phi(L_3))$,
% we get that the embedding points of $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$ 
% are collinear in their original order. 
$\\ \\$
% --------------------------------------------------------------------------------------
% $\\ \\$
We have already shown that $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$ is a straight line.
If these embedding points are collinear with $\phi(p_1)$ and $\phi (L_4) \cap ( \phi (L_1) \cup \phi (L_2))$ (see Figure \ref{msgg}),
then $L_4$ is preserved. Otherwise, the embedding points of  $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$
are collinear with $\phi(p_1)$ and $\phi(p_2)$, as $\phi(p_2)$ and $\phi(L_1) \cap \phi(L_4)$
are the only two embedding points of $\phi(L_1)$ that 
are not adjacent to all embedding points of $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$.
% 
% all of them are not adjacent to.
% 
% Now consider 
% the horizontal lines emanating from $\phi(p_1)$. Since all the embedding points of $\phi(L_4)$
% see all the embedding points of $\phi(L_1)$ except $\phi(p_2)$ and $\phi(L_1) \cap \phi(L_4)$, 
% then the embedding points of $\phi(L_4)$ lie either on the line through $\phi(p_1)$ and $\phi(p_2)$ or 
% on the line through $\phi(p_1)$ and $\phi(L_1) \cap \phi(L_4)$.
Observe that since the embedding points of $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$
form either a straight line or a reflex chain facing $\phi(p_2)$,
there cannot be any other embedding point on the line passing through $\phi(p_1)$ and $\phi(p_2)$.
So, the embedding points of $\phi(L_4) \setminus (\phi(L_1) \cup \phi(L_2) \cup \{ \phi(p_1) \})$
must lie on the line through $\phi(p_1)$ and $\phi(L_1) \cap \phi(L_4)$.
Furthermore, since the adjacency relationships between the embedding points of $\phi(L_4)$ cannot change, $L_4$ is preserved. 
% As $L_4$ is preserved, and $vert \phi(L_3) \vert = \vert \phi(L_4) \vert$ 
Since all segments between embedding points of $\phi(L_4)$ and $\phi(p_2)$ require distinct
embedding points of $\phi(L_3)$, and $\vert \phi(L_3) \vert = \vert \phi(L_4) \vert$,
every embedding point of $\phi(L_3)$ must lie on the horizontal line passing through $\phi(p_1)$ and $\phi(L_1) \cap \phi(L_3)$.
Since they are all collinear and the adjacency relationships between the embedding points of $\phi(L_3)$ cannot change, $L_3$ is also preserved.
\end{proof} 
\begin{lemma} \label{uemsgg}
 Let $G$ be a modified slanted grid graph with visibility embedding $\xi$ (Figure \ref{msgg}).
$G$ has a unique visibility embedding, up to the preservation of lines.
\end{lemma}
\begin{proof} 
By Lemma \ref{4lp}, $L_1$, $L_2$, $L_3$ and $L_4$ are preserved. 
Let $\xi'$ be any other visibility embedding of $G$. 
Let $\phi$ denote the bijection between $\xi$ and $\xi'$. So, $\phi(L_1)$, $\phi(L_2)$, $\phi(L_3)$ and $\phi(L_4)$ are  
the images of $L_1$, $L_2$, $L_3$ and $L_4$ in $\xi'$, respectively.
$\\ \\$
% 
% 
% 
Consider any horizontal line $L_i$ in $\xi$ passing through the embedding points $\{ p_1, p_{i_1}, p_{i_2}, \ldots, p_{i_j}\}$,
where $p_{i_1}$ and $p_{i_2}$ lie on $L_1$ and $L_2$ respectively. In $\xi'$,
all the embedding points of $\phi(L_1) \setminus \{ \phi(p_2) \cup \phi(p_{i_1}) \}$ 
are adjacent to all the embedding points of 
$\phi(L_i) \setminus \{\phi(p_{i_1}), \phi(p_{i_2})  \}$.
On the other hand, by the arguments 
of Lemma \ref{4lp}, the embedding points of $\phi(L_i) \setminus \{\phi(p_{i_1}), \phi(p_{i_2})  \}$ cannot
lie on the line passing through $\phi (p_1)$ and $\phi(p_2)$. 
Hence, the embedding points of $\phi(L_i) \setminus \{\phi(p_{i_1}), \phi(p_{i_2})  \}$
must lie on the horizontal line passing through $\phi (p_1)$ and $\phi(p_{i_1})$.
Since $L_1$ and $L_2$ are preserved, and $\vert L_1 \vert = \vert L_2 \vert$, 
$\phi(p_{i_2})$
must also lie on the horizontal line passing through $\phi (p_1)$ and $\phi(p_{i_1})$.
Since the adjacency relationships between the embedding points of $\phi(L_i)$ cannot change, 
the embedding points of $\phi(L_i)$ are collinear in the order of their pre-images in $L_i$.
This property is also true for all vertical lines and all other horizontal lines.
Hence, all horizontal and vertical lines of $\xi$ are preserved.
% 
% 
% 
% $\phi(p_{i_1})$ is the only
% embedding point on $\phi (L_1)$ that is adjacent to none of 
% the embedding points in $\phi(L_i) \setminus \{\phi(p_{i_1}), \phi(p_{i_2})  \}$.   
% 
% $\\ \\$
% Consider any embedding point
% $\phi(p_i)$ of $\xi \setminus(\phi(L_1) \cup \phi(L_2) \cup \phi(L_3) \cup \phi(L_4))$. The embedding point $p_i$ is non-adjacent to 
% exactly one embedding point of $L_1$ (say, $p'$) and one embedding point of $\phi(L_3)$ (say, $p''$). Hence, 
% a unique line $L$ passing through 
%  $p_1$ and $p'$, and one line $L'$ passing through $p_2$ and $p''$ such that $p_i$ is on the intersection of $L$ and $L'$. 
% Therefore, all the vertical lines and all the horizontal lines are preserved. 
% $\\ \\$
Consider a non-horizontal and non-vertical line passing through embedding points of $\xi$.
All such lines pass through exactly two embedding points of $\xi$ and it can be seen that these lines are also preserved.
Hence, $G$ has a unique visibility embedding, up to the preservation of lines.
% $\\ \\$
% It remains to argue that 
% the ordinary lines are preserved. Consider two embedding points $p_j$ and $p_k$ defining an ordinary line. Therefore, in 
% any embedding of $G$, the images $p_j$ and $p_k$ are visible from each other. Thus, the ordinary line between $p_j$ and $p_k$ is
%  preserved in any embedding of $G$.
\end{proof}
% $\\ $
% For every vertical line $l'$ we refer to the vertex  on $l'$ adjacent to $\phi(p_2)$ as the \emph{topmost vertex} of $l'$.
% The next vertex on the same vertical line, adjacent to the topmost vertex but not to $p_2$,
% is called the \emph{second topmost vertex} of $l'$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  3-SAT GRAPH  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{A 3-SAT graph} \label{sec3sat}
% 
% 
In this section, we first construct a \emph{3-SAT graph} $G'$, corresponding to a 3-SAT formula $\theta$
 of $n$ variables $\{ x_1, x_2, \ldots, x_n \}$ and $m$ clauses $\{ C_1, C_2, \ldots, C_m \}$.
 Then $G'$ is embedded into $G$ to construct a \emph{reduction graph} $G''$ such that 
 $G''$ is a PVG if and only if $\theta$ is satisfied.
 An embedding of $G''$ consists of regions called \emph{variable patterns} and \emph{clause patterns} respectively.
The number of clause patterns and variable patterns correspond to the number of clauses and variables respectively, in $\theta$.
%  $\\ \\$
% In this section, we describe the construction of the \emph{3-SAT graph} $G'$ and \emph{reduction graph} $G''$ of a given 3-SAT formula.
% Let $\phi$ be a 3-SAT formula with $n$ variables $\{ x_1, x_2, \ldots, x_n \}$ and $m$ clauses $\{ C_1, C_2, \ldots, C_m \}$.
% Let $n_{k}$ be the number of clauses of $\phi$ in which $x_i$ occurs.
% Similarly, let $n_{\overline{k}}$ be the number of clauses of $\phi$ in which $\overline{x_i}$ occurs.
% Let $G$ be an MSGG derived from the  $1600(mn + m + n)^2 \times 1600(mn + m + n)^2$ SGG. $G$ is the MSGG of $\phi$.
% $ \\ \\$ 
% After obtaining $G''$ from $G'$, we will show that $G''$ has a visibility embedding if and only if $\phi$ is satisfiable. 
\subsection{Construction of a 3-SAT graph} \label {consalg}

% $\\ \\$
% -------------------------------------------------------------------------------------------------------
% $\\ \\$
The construction of a 3-SAT graph $G'$ is described with respect to the unique visibility embedding $\xi$ of $G$.
% Note that this embedding might not remain a visibility embedding as the vertices of $G'$ are embedded into it
% as shown in Lemma \ref{uemsgg}.
Initially, $G$ is constructed from a slanted grid graph of $1600(mn + m + n)^2 \times 1600(mn + m + n)^2$ vertices,
by the process stated in Section \ref{consmsgg}.
% Using a slanted grid graph of $1600(mn + m + n)^2 \times 1600(mn + m + n)^2$ vertices, $G$ is
% constructed by the procedure stated in Section \ref{consmsgg}.
We know that the vertices of $G$ are placed as embedding points on the intersection points of horizontal and vertical lines of $\xi$.
Recall that there are intersection points in $\xi$ that do not contain any embedding point corresponding to the vertices of $G$.
We wish to use these free intersection points for embedding points corresponding to the vertices of $G'$.
% Recall that there are no embedding points on the intersection points of the horizontal lines $\{  \}$
% with the vertical
Embedding points corresponding to vertices of $G'$ are placed on the free intersection points in such a way
that they correspond to the variables and clauses of $\theta$.
For every vertical line $l$ in $\xi$,
we refer to the embedding point on $l$ adjacent to $p_2$ as the \emph{topmost embedding point} of $l$,
and the next embedding point of $l$  
is called the \emph{second topmost embedding point} of $l$.
 The vertices of $G'$ are classified into the following six types.
 \begin{enumerate}
  \item \emph{\textbf{Occurrence vertices (o-vertices):}}
  Let $n_{i}$ and $\overline{n_{i}}$ be the number of clauses of $\theta$ in which $x_i$ and $\overline{x_i}$ occur, respectively.
  A group of vertices of size $(n_{i} + \overline{n_{i}} + 2)$ in $G'$ corresponding to $x_i$ and $\overline{x_i}$ in $\theta$
  are referred to as \emph{o-vertices} of $x_i$ in $G'$.
  The o-vertex corresponding to $x_i$ (or, $\overline{x_i}$) in $C_j$ is denoted as 
$o_{i,j}$ (respectively, $\overline{o}_{{i},j}$). Two more o-vertices of $x_i$
are denoted as $o_{i,0}$ and $\overline{o}_{{i},0}$ respectively.
  The embedding points corresponding to o-vertices are called
  \emph{o-points} (Figure \ref{varpat}). For each $x_i$,  o-points are embedded on two distinct vertical lines of $\xi$ called the 
  \emph{left o-line} and \emph{right o-line} of $x_i$, respectively (Figure \ref{varpat}). 
  The left o-line and right o-line contain all the o-points corresponding to $x_i$ and $\overline{x_i}$, respectively.
 The o-points embedded on the left o-line (or, the right o-line) 
 are called the \emph{left o-points} (respectively, \emph{right o-points}) of $x_i$ and their corresponding vertices are called
 the \emph{left o-vertices} (respectively, \emph{right o-vertices}) of $x_i$.
 
  \item  \emph{\textbf{Truth value vertices (t-vertices):}} For every variable $x_i$ there exists exactly one vertex 
  of $G'$ called the \emph{t-vertex} of $x_i$ (denoted as $t_i$), and its corresponding embedding point is called the \emph{t-point}
  of $x_i$ (Figure \ref{varpat}). For a given assignment of variables in $\theta$, $x_i$ can be $1$ or $0$.
%   
%   
%   the t-vertex is embedded on one of the o-lines 
%   of $x_i$ according to the value assigned to $x_i$.
%   If $x_i$ is assigned $1$, then the t-point of $x_i$
%   is embedded as the bottom most embedding point of the left o-line of $x_i$.
%   Otherwise, if $x_i$ is assigned $0$, then the t-point of $x_i$
%   is embedded as the topmost embedding point of the right o-line of $x_i$, restricted to $G'$.
  If $x_i=1$ (or, $0$), then the t-vertex of $x_i$ is embedded as the lowermost (respectively, uppermost) embedding point, 
  corresponding to $G'$ on the left (respectively, right) o-line of $x_i$.
%   
%   These vertices correspond to the occurrence of a variable and its complement in the clauses of $\theta$.
%   For each variable $x_i$ of $\theta$, its o-vertices are embedded on two distinct vertical lines called the \emph{o-lines} of $x_i$. 
 \item \emph{\textbf{Clause vertices (c-vertices):}} 
 For every clause $C_j$, there exists exactly one vertex 
  of $G'$ called the \emph{c-vertex} of $C_j$ (denoted as $c_j$), and its corresponding embedding point is called the \emph{c-point}
  of $C_j$ (Figure \ref{clpat}).
  The rightmost vertical line of the clause pattern of a clause $C_j$ is called the \emph{c-line} of $C_j$.
 The c-point of $C_j$ is embedded as the lowermost embedding point of the c-line of $C_j$.
  \item \emph{\textbf{Literal vertices (l-vertices):}} 
  These vertices also correspond to the occurrence of a variable and its complement in the clauses of $\theta$, and their
  corresponding embedding points are called \emph{l-points} (Figures \ref{varpat} and \ref{clpat}).
  Visibility of a t-point of a variable needs to be blocked 
  from the o-points of one of its o-lines. Visibility of the c-point
  of a clause also needs to blocked from the second topmost embedding point of the vertical line in which it is embedded. The 
  l-points are used 
  as blockers in these cases. 
  An l-point corresponding to $x_i$ occurring in $C_j$ can be used to block either the t-point of $x_i$ from a left o-point
  of $x_i$, or the c-point of $C_j$ from the second topmost embedding point of the c-line of $C_j$. 
  The l-vertex corresponding to the embedding points used for blocking the visibility of 
  $t_i$ from $o_{i,j}$ (or, $\overline{o}_{{i},j}$), is denoted as 
$l_{i,j}$ (respectively, $\overline{l}_{{i},j}$).
  \item \emph{\textbf{Dummy vertices (d-vertices):}} 
  For each variable $x_i$, there is exactly one vertex in $G'$ called the \emph{d-vertex}
  of $x_i$ (denoted as $d_i$), and its corresponding embedding point in $\xi$ is called the \emph{d-point} of $x_i$ (Figure \ref{varpat}).
  The d-points are sometimes
  required to block the visibility of o-points from the second topmost embedding point of their vertical line.
  The rightmost vertical line of the variable pattern of $x_i$ is called the \emph{d-line} of $x_i$.
  If $x_i$ is assigned $1$, then the d-point is embedded on the right o-line of $x_i$. Otherwise it is embedded on the
  d-line of $x_i$.
  \item \emph{\textbf{Blocking vertices (b-vertices):}}
  These vertices of $G'$ correspond to
  embedding points called \emph{b-points} (Figures \ref{varpat} and \ref{clpat}).
  The b-points are required to block the visibility between $(i)$ d-points and o-points, 
  $(ii)$ t-points and the topmost embedding points of o-lines,
  and $(iii)$ l-points and the topmost embedding points 
  of several vertical lines.
  The vertical lines on which b-points are embedded are called \emph{b-lines}.
  $\\ \\$
  There are five types of b-vertices.
  The b-vertices corresponding b-points that are used to block the visibility of embedding points of $t_i$ and $d_i$ 
  from the topmost embedding points of the corresponding d-line o-lines, are denoted as $b^1_{i},  b^2_{i},  b^3_{i},  b^4_{i}$.
  The b-vertex corresponding to the b-point that is used to block the visibility of $t_i$ from the topmost embedding point of 
  the o-line of $o_{i,j}$ (or, $\overline{o}_{i,j}$), is denoted as $b_{i,j}$ (respectively, $\overline{b}_{{i},j}$).
  The b-vertex corresponding to the b-point that is used to block the d-point of $d_i$ from the o-point of
  $\overline{o}_{i,j}$ is denoted as $\overline{b}^d_{{i},j}$.
  The b-vertices corresponding to b-points that are used to block 
  the l-point of $l_{i,j}$ (or, $\overline{l}_{{i},j}$) in the clause pattern of $C_j$, from the topmost
  embedding points of its corresponding o-line or c-line, are denoted as 
   $b^l_{i,j}$ and $b^r_{i,j}$
  (respectively, $\overline{b}^l_{{i},j}$ and $\overline{b}^r_{{i},j}$). 
  The two b-vertices corresponding to the c-line of $C_j$ are denoted as $b^c_{j,1}$ and $b^c_{j,2}$.
%   The b-points corresponding to $b^c_{j,1}$ and $b^c_{j,2}$ are used to block the visibility of the l-point on the c-line of $C_j$
%   from the topmost embedding points of two other vertical lines.
  The b-points corresponding to $b^c_{j,1}$ and $b^c_{j,2}$ are embedded on the two vertical lines immediately to the left of the c-line of $C_j$.
%  \item \emph{\textbf{Literal vertices (l-vertices):}} The embedding points corresponding to the a-vertex of a variable needs to be blocked 
%   from embedding points corresponding to the o-vertices of one of its o-lines. The embedding point corresponding to the c-vertex
%   of a clause also needs to blocked from the second topmost vertex of the vertical line that it is embedded in. The embedding points 
%   corresponding to l-vertices are used 
%   as blockers in these cases.
%  These vertices correspond to the clauses of $\theta$
%    and are embedded in the corresponding clause patterns in $\xi$. Each clause pattern has exactly one 
%    c-vertex. The vertical line on which a c-vertex is embedded is called a \emph{c-line}.
  \end{enumerate}
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a46_f.pdf,width=0.790\hsize}}}
\caption{
The variable pattern for $x_i$. 
The t-point, o-points, l-points, d-point and b-points are shown in the figure,
along with the names of their corresponding vertices.
The gray areas represent multiple horizontal lines.
Non-edges are drawn as curves. The lines $l_1$ and $l_2$ are the left and right o-lines 
of $x_i$ respectively.
% The a-vertex, d-vertex, o-vertices, l-vertices and b-vertices are coloured in 
% red, orange, yellow, green and blue respectively.
}
\label{varpat}
\end{center}
\end{figure}
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a48_f.pdf,width=0.34\hsize}}}
\caption{
The clause pattern for $C_j$.
The c-point, l-points and b-points are shown in the figure, along with the names of their corresponding vertices.
The gray areas represent multiple horizontal lines.
Non-edges are drawn as curves.
The line $l_3$ is the c-line of $C_j$.
% 
% The c-vertex, l-vertices and b-vertices are coloured in red, green and blue respectively.
% The non-edges are coloured in red.
}
\label{clpat}
\end{center}
\end{figure}
Based on the above classifications, we present the construction of $G'(V',E')$. The sets of vertices   
associated with $x_i$ and $C_j$ are denoted as $V^x_i$ and $V^c_j$ respectively.
Each $V^x_i$ contains the vertices $\{ t_i, d_i, o_{i,0}, \overline{o}_{{i},0}, b^1_{i},  b^2_{i},  b^3_{i},  b^4_{i} \}$.
For every $C_j$ containing $x_i$ (or, $\overline{x_i}$), $V^x_i$ contains the vertices
$\{ o_{i,j},l_{i,j},b_{i,j}  \}$
(respectively, $\{ \overline{o}_{{i},j}, \overline{l}_{{i},j}, \overline{b}_{{i},j}, \overline{b}^d_{{i},j}\}$).
Each $V^c_j$ contains $c_j$, and $\{ b^l_{i,j}, l_{{i},j} ,b^r_{i,j}\})$ 
(or, $\{\overline{b}^l_{{i},j}, \overline{l}_{{i},j} ,\overline{b}^r_{{i},j} \}$) 
corresponding to each $x_i$ (respectively, $\overline{x_i}$)
in $C_j$. Hence,
\begin{eqnarray*}
 V^x_i &=& \{ t_i, d_i, o_{i,0}, \overline{o}_{{i},0} \} \cup ( \bigcup_{x_i \in C_j} \{ o_{i,j},l_{i,j},b_{i,j}  \} )
 \cup ( \bigcup_{\overline{x_i} \in C_j} \{ \overline{o}_{{i},j}, \overline{l}_{{i},j}, \overline{b}_{{i},j}, \overline{b}^d_{{i},j}\} )
 \cup \{ b^1_{i},  b^2_{i},  b^3_{i},  b^4_{i}\}\\ 
 V^c_j &=&   \{ c_j \} \cup ( \bigcup_{x_i \in C_j} \{ b^l_{i,j}, l_{{i},j} ,b^r_{i,j}\}) \cup
 (\bigcup_{\overline{x_i} \in C_j} \{\overline{b}^l_{{i},j}, \overline{l}_{{i},j} ,\overline{b}^r_{{i},j} \})
   \cup \{ b^c_{j,1}, b^c_{j,2} \} \\
 V' &=& (\bigcup_{x_i \in \theta} V^x_i) \cup (\bigcup_{C_j \in \theta} V^c_j) \\
\end{eqnarray*}
% 
% $\\ \\$
\noindent For every $x_i, x_k \in \theta$, each vertex of $V^x_i$ is adjacent to every vertex of $V^x_k$.
Similarly, for every $C_j, C_k \in \theta$, each vertex of $V^c_k$ is adjacent to each vertex of $V^c_k$.
% Also, for every 
The set of edges among vertices
of $V^x_i$ (or, $V^c_j$) is denoted as $E^x_i$ (respectively, $E^c_j$). 
% Similarly, the set of edges among vertices of $V^c_j$ is denoted as 
% $E^c_j$.
All vertices of $V^x_i$ are adjacent to each other except the o-vertices, and all left o-vertices
are adjacent to all right o-vertices. The left o-vertices (or, right o-vertices) along with $t_i$ induce a path in $G'$. 
% Similarly,
% the right o-vertices along with $t_i$ induce a path.
The right o-vertices and $d_i$ induce a path in $G'$ as well.
All vertices of $E^c_j$ are adjacent to each other. 
For every $x_i, C_j \in \theta$, each vertex of $V^x_i$ is adjacent to each vertex of $V^c_j$.
% All the vertices in separate vertex sets of different
% variables and clauses are adjacent to each other.
% Hence the combinatorial structure of $G'$ can be stated as follows.
Hence,
\begin{eqnarray*}
%  V^x_i &=& \{ t_i, d_i, o_{i,0}, \overline{o}_{{i},0} \} \cup ( \bigcup_{x_i \in C_j} \{ o_{i,j},l_{i,j},b_{i,j}  \} )
%  \cup ( \bigcup_{\overline{x_i} \in C_j} \{ \overline{o}_{{i},j}, \overline{l}_{{i},j}, \overline{b}_{{i},j}, \overline{b}^d_{{i},j}\} )
%  \cup \{ b^1_{i},  b^2_{i},  b^3_{i},  b^4_{i}\}\\ 
%  V^c_j &=&   \{ c_j \} \cup ( \bigcup_{x_i \in C_j} \{ b^l_{i,j}, l_{{i},j} ,b^r_{i,j}\}) \cup
%  (\bigcup_{\overline{x_i} \in C_j} \{\overline{b}^l_{{i},j}, \overline{l}_{{i},j} ,\overline{b}^r_{{i},j} \})\\
%  V' &=& (\bigcup_{x_i \in \theta} V^x_i) \cup (\bigcup_{C_j \in \theta} V^c_j) \\
 E^x_i &=& \{ (v_a,v_b) \mid v_a \neq v_b \ and  \ v_a,v_b  \in V^x_i \setminus ( \{ o_{i,0}, \overline{o}_{{i},0} \}
 \cup  ( \bigcup_{x_i \in C_j} \{ o_{i,j} \}) \cup ( \bigcup_{\overline{x_i} \in C_j} \{ \overline{o}_{{i},j} \})\} \\
  & & \cup \{ (v_a,v_b) \mid v_ a \in \{ o_{{i},0} \} \cup  ( \bigcup_{x_i \in C_j} \{ o_{i,j} \})
  \ and \ v_b \in \{ \overline{o}_{{i},0}  \} \cup ( \bigcup_{\overline{x_i} \in C_j} \{ \overline{o}_{{i},j} \}) \}\\
%  
 & &\cup   \{ (v_a,v_b) \mid v_ a \in \{ o_{i,0}, \overline{o}_{{i},0} \}
 \cup  ( \bigcup_{x_i \in C_j} \{ o_{i,j} \}) \cup ( \bigcup_{\overline{x_i} \in C_j} \{ \overline{o}_{{i},j} \}
 \ and  \\
 & & v_b  \in V^x_i \setminus ( \{ t_i, d_i, o_{i,0}, \overline{o}_{{i},0} \}
 \cup  ( \bigcup_{x_i \in C_j} \{ o_{i,j} \}) \cup ( \bigcup_{\overline{x_i} \in C_j} \{ \overline{o}_{{i},j} \})\} \\
 & &\cup \{ (t_i,o_{i,0}), (t_i,\overline{o}_{{i},0}), (d_i,\overline{o}_{{i},0}) \}
 \cup \{ (d_i,v_b) \mid v_b \in ( \bigcup_{x_i \in C_j} \{ o_{i,j} \}) \} \\ 
 & & \cup \{ (o_{i,j},o_{i,k}) \mid j < k \ and \ \nexists o_{i,l} \in V^x_i : i<l<k \} \\
  & & \cup \{ (\overline{o}_{i,j},\overline{o}_{i,k}) \mid j < k \ and \ \nexists \overline{o}_{i,l} \in V^x_i : i<l<k \} \\
%  
%  
 E^c_j &=& \{ (v_av_b) \mid v_a \neq v_b \ and \ v_a,v_b \in V^c_j \} \\
%  
 E' &=& \{ \bigcup_{x_i\in \theta}  E^x_i \} 
 \cup \{ \bigcup_{C_j\in \theta} E^c_j \} 
 \cup (\bigcup_{x_i\in \theta}\{ (v_a,v_b) \mid v_a \in V^x_i \ and \ v_b \in V' \setminus V^x_i   \}) \\
 & & \cup (\bigcup_{C_j\in \theta} \{ (v_a,v_b) \mid v_a \in V^c_j \ and \ v_b \in V' \setminus V^c_j \} )
%  & &\cup \{ o_{n_i,0}, o_{i,1}, \ldots, o_{i,n_i} \}             
%                \cup \{ \overline{o}_{{i},0}, o_{\overline{i},1}, \ldots, o_{\overline{i},\overline{n_i}} \}  \\
\end{eqnarray*}
% \begin{enumerate}
%  \item 
% \end{enumerate}
% We construct $G$, an MSGG derived from the  $1600(mn + m + n)^2 \times 1600(mn + m + n)^2$ SGG. 
We have the following lemma on the size of $G'$.
\begin{lemma}\label{num}
There are $(8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i})$ vertices in $G'$.
\end{lemma}
\begin{proof}
We know from the construction of $G'$ that  
the number of t-vertices is $n$,
the number of d-vertices is $n$,
the number of o-vertices is $(3m+2n)$,
the number of l-vertices is $3m$,
the number of c-vertices is $m$,
and  
the number of b-vertices is $(4n + 11m + \sum\limits_{x_i \in \theta}\overline{n_i})$
in $G$.
So, $G'$ has a total of
$(8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i})$ vertices.
%   
% There are a total of $n$ t-vertices, $n$ d-vertices, $(3m+2n)$ o-vertices, $3m$ l-vertices, $m$ c-vertices and 
% $(4n + 11m + \sum\limits_{x_i \in \theta}\overline{n_i})$ b-vertices of $G'$. So, $G'$ has a total of
% $(8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i})$ vertices.
\end{proof}
\subsection{Construction of a reduction graph}\label{subsecconsred}

Here, we construct the reduction graph $G''(V'',E'')$ 
such that 
 $G''$ is a PVG if and only if $\theta$ is satisfied.
From Lemma \ref{num},
we know that the number of vertices in $G'$ is $(8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i})$.
To get $G''$ with certain restrictions on its possible visibility embeddings, we need to join
$G'$ to a modified slanting grid graph $G$ with edges such that $\vert G \vert \sim \vert G' \vert ^{16}$.
% 
% $\\ \\$
Since $20(m+n) > (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i})$, 
the modified slanted grid graph $G(V,E)$ is constructed
% a
% $400(m+n)^2 \times 400(m+n)^2$ slanting grid graph is able to maintain certain restrictions
% on the possible visibility embeddings of $G''$.
% 
% we get an estimate of the number of vertices required for the corresponding MSGG.
% So, 
starting from a $400(m+n)^2 \times 400(m+n)^2$ slanting grid graph, as stated
in Section \ref{consmsgg}.
$\\ \\$
The vertices of $G''$ are the vertices of $G$ and $G'$. Hence,
% \begin{eqnarray*}
 $V'' = V \cup V'$. 
% \end{eqnarray*}
Consider the unique visibility embedding of $G$, with $p_1$ and $p_2$ as the rightmost and topmost embedding points, respectively.
The $ith$ horizontal line from the top 
and 
the $ith$ vertical line from the left 
are denoted by $l^h_i$ and $l^v_i$ respectively.
% is denoted by $l^h_i$. 
% The $ith$ vertical line from the left is denoted by $l^v_i$. 
The vertex of $V$ that corresponds to the embedding point at the intersection of the $ith$ vertical and $jth$ horizontal lines, 
is denoted by $v(l^v_i, l^h_j)$. Now we assign similar coordinates to vertices of $V'$. Note that we may assign multiple
pairs of coordinates to the same vertex, in order to facilitate the analysis of embeddings of $G''$.
$\\ \\$
% \begin{enumerate}
%  \item We construct $G$, an MSGG derived from the  $1600(mn + m + n)^2 \times 1600(mn + m + n)^2$ SGG. 
% 
%  \item 
 For each variable $x_i \in \theta$, coordinates are assigned to vertices of $V^x_i$ as follows (Figure \ref{varpat}).
 \begin{enumerate}[(i)]
  \item Let $a = 400(m+n)^2 + n -  (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i}) 
 + 12m - 1$,
%  6m + \sum _{k=1} ^{i-1} (2n_{k} +3 n_{\overline{k}} +6)$,
  $b =   2(20(m+n))^8 + \sum _{k=1} ^{i-1} (2n_{k} + 3\overline{n_{{k}}} +7)$,
  and $c=  \sum _{k=1} ^{i-1} (2n_{k} + 3\overline{n_{{k}}} + 3)$.
  \item Assign coordinates $(l^v_{b+1},l^h_{a+ 4n+c + 2n_{i} +2 })$
and  $(l^v_{b+2n_{i}+3},l^h_{a+ 4n+c + 2n_{i} +2 })$ to $t_i$. 
  \item Assign coordinates $(l^v_{b+1},l^h_{a+ 4n+c + n_{i} + 1 })$
  and $(l^v_{b+2n_{i}+3},l^h_{a+ 4n+c + 2n_{i} +2\overline{n_{i}} + 3})$
  to $o_{i,0}$ and $\overline o_{i,0}$ respectively. 
%   $\\ \\$
%    We embed vertices on the points of intersection of $l^v_{b+1}$ and $\{ l^h_{a+ 4n+c + 1 },$ 
%  $l^h_{a+ 4n+c + 2 },$ $\ldots,$ $l^h_{a+ 4n+c + n_{i} + 1 } \}$.
  \item Recall that the left o-vertices of $x_i$ induce a path along with $t_i$ in $G'$. Let 
  $S = (o_{i,l}, \ldots, o_{i,0}, t_i)$ be the sequence of vertices in the path. Note that 
  $S$ has $n_i +2$ elements. 
  For each $o_{i,j} \in S$, $j \neq 0$, assign the coordinates $(l^v_{b+1},l^h_{a+ 4n+c + k})$
  to $o_{i,j}$, where $o_{i,j}$ is the $k^{th}$ element of $S$.
   \item Similarly, the right o-vertices of $x_i$ induce a path along with $t_i$ in $G'$. Let 
  $\overline{S} = (t_i, \overline o_{i,0}, \ldots, \overline o_{i,l})$ be the sequence of vertices in the path. Note that 
  $S$ has $\overline{n_i} +2$ elements. 
  For each $\overline o_{i,j} \in \overline S$, $j \neq 0$, assign the coordinates
  $(l^v_{b+2n_{i}+ 2\overline{n_{i}} +5}, l^h_{a+ 4n+c + 2n_{i} +2\overline{n_{i}} + 3 + k})$
  to $\overline o_{i,j}$, where $\overline o_{i,j}$ is the $(k+2)^{th}$ element of $\overline S$.
%   $\\ \\$
%    $\{ l^h_{a+ 4n+c + 1 },$ 
%  $l^h_{a+ 4n+c + 2 },$ $\ldots,$ $l^h_{a+ 4n+c + n_{i} + 1 } \}$.
%   be the sequence 
%   \item 
%   Starting from $k = 1$, let $k$ be the rank of the 
%   $ \\ \\$
%   For each $o_i,j$ in $V^x_i$, assign the coordinate 
%   $(l^v_{b+1}, $ and $\{ l^h_{a+ 4n+c + 1 },$ 
%  $l^h_{a+ 4n+c + 2 },$ $\ldots,$ $l^h_{a+ 4n+c + n_{i} + 1 } \}$
%   $\\ \\$
%   to $o_i,j$.
\item To each l-vertex $l_{i,j}$, assign coordinates $(l^v_{b+1+2k},l^h_{a+ 4n+c + n_{i} + 1 +k })$,
where  $o_{i,j}$ is the $k^{th}$ element of $S$, 
The line $l^v_{b+1+2k}$ is called an \emph{associated-line} of $l_{i,j}$.
\item Similarly, to each l-vertex $\overline l_{i,j}$ assign coordinates $(l^v_{b+n_{i}+ 1 + 2k},l^h_{a+ 4n+c + 2n_{i} + 2 + k })$,
where  $\overline o_{i,j}$ is the $(k+2)^{th}$ element of $\overline S$. 
The line $l^v_{b+1+2k}$ is called an associated-line of $\overline l_{i,j}$.
% $\\ \\$
% $ \{ (l^v_{b+n_{i}+3},l^h_{a+ 4n+c + 2n_{i} + 3 }), $
% $(l^v_{b+n_{i}+5},l^h_{a+ 4n+c + 2n_{i} + 4 }), $
% $\ldots, (l^v_{b+n_{i}+2\overline{n_{i}}+1},l^h_{a+ 4n+c + 2n_{i} +\overline{n_{i}} + 2 }) \} $
%  $\\ \\$
%   $ \{ (l^v_{b+3},l^h_{a+ 4n+c + n_{i} + 2 }),$
%  $(l^v_{b+5},l^h_{a+ 4n+c + n_{i} + 3 }),$
%  $\ldots,$  \\
%  $(l^v_{b+n_{i}+1}, l^h_{a+ 4n+c + 2n_{i} + 1 }   )   \} $
  \item Assign coordinates  $(l^v_{b+2n_{i}+2},l^h_{a+ 4n+c + 2n_{i} +2 })$
  and $(l^v_{b+ 2n_{i} + 3\overline{n_{i}} +7},l^h_{a+ 4n+c + 2n_{i} +2 })$ to $d_i$.
 \item Assign coordinates $(l^v_{b+2}, l^h_{4(n-i)+4})$,
 $(l^v_{2(n_{i}+ \overline{n_{i}})+3}, l^h_{4(n-i)+3} )$,
 $(l^v_{2(n_{i}+ \overline{n_{i}})+5} , l^h_{4(n-i)+2})$ and 
 $(l^v_{2n_{i}+ 3\overline{n_{i}}+6}, l^h_{4(n-i)+1})$ to the b-vertices $b^1_{i}$, $b^2_{i}$, $ b^3_{i}$ and $b^4_{i}$ respectively.
 \item
%  Assign the coordinates $(,)$ 
%  $\\ \\$
 Let $e = 400(m+n)^2 + n -  (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i}) +
 \sum _{p=i} ^{n} (n_{p} + n_{\overline{p}}) + 12m - 1$.
 Assign coordinates $(l^v_{b+2 + 2k},l^h_{e+n_{i} + \overline{n_{i}} +1 -k})$ to $b_{i,j}$,
 where  $o_{i,j}$ is the $k^{th}$ element of $S$.
 Similarly, assign coordinates $(l^v_{b+2n_i + 2 + 2k},l^h_{e+n_{i} + \overline{n_{i}} -n_i +1 -k})$ to $\overline b_{i,j}$,
 where  $\overline o_{i,j}$ is the $(k+2)^{th}$ element of $\overline S$.
%  $\\ \\$
% We embed vertices on the set of points $\{ (l^v_{b+4}, l^h_{e+n_{i} + \overline{n_{i}} }      ),$
% $(l^v_{b+6},l^h_{e+n_{i} + \overline{n_{i}}-1} ),$
% $\ldots,$
% $(l^v_{b+ 2(n_{i}+\overline{n_{i}})+2}, l^h_{e+n_{p} + 1} ) \}$.
 \item Assign coordinates 
 $\{ (l^v_{2(n_{i}+ \overline{n_{i}})+5+k},   l^h_{a+ 4n+c + 2n_{i} +2\overline{n_{i}} + 3 -k} )$
 to each $\overline{b}^d_{i,j}$, where
  $\overline o_{i,j}$ is the $(k+2)^{th}$ element of $\overline S$.
%  $\\ \\$
%  $\{ (l^v_{2(n_{i}+ \overline{n_{i}})+5+k},   l^h_{a+ 4n+c + 2n_{i} +2\overline{n_{i}} + 3 -k} ),$
%  $(l^v_{2(n_{i}+ \overline{n_{i}})+7}, l^h_{a+ 4n+c + 2n_{i} +2\overline{n_{i}} + 1}  ),$
%  $\ldots,$
%  $(l^v_{2n_{i}+ 3\overline{n_{i}}+5},  l^h_{a+ 4n+c + 2n_{i} +\overline{n_{i}} +3} ) \}$.
%  \item
 % $l^v_{b+n_{i}+3}$ and $l^v_{b+n_{i}+4}$. 
% $l^v_{b+2n_{i}+2}$ and $l^v_{b+2n_{i}+3}$.
 \end{enumerate}
% 
%  
%   \item 
%  For each pair of coordinates $()$ assigned to a 
%  vertex $v$, 
 For each clause $C_j \in \theta$ , coordinates are assigned to the vertices of $V^c_j$ as follows (Figure \ref{clpat}).
   \begin{enumerate} [(i)]
   \item  Let $f = (\sum _{k=1} ^{n} (2n_{k} + 3n_{\overline{k}} +7)) + 12(j-1)$.
   Let $g =  400(m+n)^2 + n -  (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i}) 
 + m - 1       +  7(m-j+1)$.
%    \item
%    \item 
%    Assign coordinates $(l^v_{f+3p-1},)$ (or, $(l^v_{f+3p-1},l^h_{})$) to $l_{i,j}$ (respectively, $\overline{l}_{i,j}$), 
%    where $x_i$ (respectively, $\overline{x_i}$) is the $p^{th}$ variable of $C_j$.
   \item
   Assign coordinates $(l^v_{f+3p-1},l^h_y)$ and $( l^v_{f+12}, l^h_y)$ to $l_{i,j}$ (or, $\overline{l}_{i,j}$), 
   where $x_i$ (respectively, $\overline{x_i}$) is the $p^{th}$ variable of $C_j$, and $l^h_y$ is the second
   component of coordinates assigned to
   $l_{i,j}$ (respectively, $\overline l_{i,j}$) earlier. 
The line $l^v_{f+3p-1}$ is called an {associated-line} of $l_{i,j}$ (respectively, $\overline{l}_{i,j}$).
   \item Assign coordinates $(l^v_{f+3p-1},l^h_{g-3(p-1)})$ and $(l^v_{f+3p-1},l^h_{g-3p+1)})$ to $b^l_{i,j}$ and $b^r_{i,j}$
   (or, $\overline b^l_{i,j}$ and $\overline b^r_{i,j}$) respectively, where 
    $x_i$ (respectively, $\overline{x_i}$) is the $p^{th}$ variable of $C_j$.
    \item Assign coordinates $(l^v_{f+10},l^h_{})$ and $(l^v_{f+11},l^h_{})$ to $b^c_{j,1}$ and  $b^c_{j,2}$ respectively.
   \item 
   Assign coordinates
   $( l^v_{f+12}  ,  l^h_{  400(m+n)^2 }  )$
   to $c_i$.
   \end{enumerate}
%  \end{enumerate}
Before we define the edge set of $G''$, we need the following definitions related to coordinates assigned to the 
vertices of $V''$.
For every vertex $q \in V'' \setminus\{v_1, v_2 \} $, let $S^q$ be the set of all pairs of coordinates assigned to $q$.
Furthermore, for every vertex $q \in V'' \setminus\{v_1, v_2 \} $, let $S^q_x$ and $S^q_y$ be the 
sets of the first and second components, respectively, of all pairs of coordinates 
assigned to $v$. 
$\\ \\$
Consider vertices $v_a$ and $v_b$, such that $v_a \in V'$ and $v_b \in V \setminus \{v_1, v_2 \}$.
% We refer to the pair $(v_a,v_b)$ as a \emph{linear neighbouring pair} if 
% $\\ \\$
Suppose that there exists some 
$l^v_{x_1} \in S^{v_a}_x \cap S^{v_b}_x$ such that
% for some $y_1, y_2$, 
$(l^v_{x_1},l^h_{y_1}) \in S^{v_a}$ and $(l^v_{x_1},l^h_{y_2}) \in S^{v_b}$
for some $y_1$ and $y_2$. Then we refer to the pair $(v_a,v_b)$ as a \emph{vertical neighbouring pair} if 
there is no 
$v_c$ with
$v_c \neq v_a$ and $v_c \neq v_b$ and $(l^v_{x_1},l^h_{y_3}) \in S^{v_c}$ such that $y_1 < y_3 < y_2$. 
% or, $y_2 < y_3 < y_1$.
Similarly, suppose that 
there exists some 
$l^h_{y_1} \in S^{v_a}_y \cap S^{v_b}_y$ such that
% for some $y_1, y_2$, 
$(l^v_{x_1},l^h_{y_1}) \in S^{v_a}$ and $(l^v_{x_2},l^h_{y_1}) \in S^{v_b}$
for some $x_1$ and $x_2$. Then we refer to the pair $(v_a,v_b)$ as a \emph{horizontal neighbouring pair} if 
there is no 
$v_c$ with
$v_c \neq v_a$ and $v_c \neq v_b$ and $(l^v_{x_3},l^h_{y_1}) \in S^{v_c}$ such that $x_1 < x_3 < x_2$. 
% or, $x_2 < x_3 < x_1$.
Let $L(G'')$ be the set of all such vertical or linear horizontal neighbouring pairs
possible from the vertices of $V'' \setminus \{v_1, v_2 \}$.
So, we have,
% $\\ \\$
% Now we define the edge-set for $G''$ as follows.
\begin{eqnarray*}
 E'' &=& E \cup E' \cup \{ (v_a,v_b) \mid v_a \in V' \ and \ v_b \in V \setminus \{v_1, v_2 \} \ and \  \\ 
     & & ( (S^{v_a}_x \cap S^{v_b}_x)\cup(S^{v_a}_y \cap S^{v_b}_y ) = \phi  \ or \  (v_a,v_b) \in L(G'')) \}\\            
\end{eqnarray*}
Based on the construction of $G''$, we state the following lemma without proof.
\begin{figure}
\begin{center}
\centerline{\hbox{\psfig{figure=a57_f.pdf,width=1.200\hsize}}}
\caption{
A canonical embedding $\psi$ of $G''$ corresponding to the given 
3-SAT formula. 
The top two rows of embedding points are $L_3$ and $L_4$.
The o-points, b-points, l-points, c-points, t-points and d-points
are 
depicted as pale circles, dark circles, pale stars, dark stars, triangles and squares respectively.
% coloured in red, yellow, green, orange, blue and pink respectively.
The non-horizontal and non-vertical line segments constitute $S_L$.
% The line segments in $S_L$ are coloured in red.
% A 3-SAT graph embedded in its MSGG, for a particular satisfying assignment.
% The horizontal and vertical lines are shown to be parallel to each
% other instead of converging at their respective points of convergence. 
% The variable and clause patterns are shown as green rectangles.
% Non edges between l-vertices and the associated lines that they are not embedded on, are drawn with red.
}
\label{3SAT}
\end{center}
\end{figure}

\begin{lemma} \label{polytime}
 Give a 3-SAT formula $\theta$, the corresponding reduction graph $G''$ can be constructed in time polynomial 
in the size of $\theta$.
\end{lemma}
\subsection{Properties of reduction graphs} \label{propgnew} 
As stated earlier, we have shown the construction of the reduction graph $G''$
of $\theta$ in polynomial time. 
% In the previous part, we constructed the reduction graph $G''$ of $\theta$ in polynomial time.
% Here
We study here
some properties of $G''$. We need some definition before we study these properties.
% Suppose $G''$ has a visibility embedding. 
An embedding $\psi$ of $G''$ is called a 
\emph{canonical embedding} of $G''$ if (a) the embedding points of $\psi$ restricted to the vertices of $G$,
form the unique visibility embedding of $G$, and (b) for all $v_q \in G'$, the embedding point of $v_q$  
is embedded on the intersection of horizontal and vertical lines 
% corresponding to 
giving 
a pair of coordinates
that has been 
assigned to $v_q$.
Observe that in a canonical embedding,
(i) each b-point is embedded only on its
corresponding b-line, 
(ii) each c-point is embedded only on its corresponding c-line, 
(iii) each t-point is embedded only on
one of its two o-lines, 
(iv) each d-point is embedded only on either its d-line or its right o-line,
(v) each o-point is embedded only on its o-line, and
(vi) each l-point is embedded only on one of its two associated lines
or its c-line.
% $\\ \\$
% $\\ \\$
If a canonical embedding $\psi$ of $G''$ is also a visibility embedding of $G''$, 
then $\psi$ is called a \emph{canonical visibility embedding} of $G''$.
% Suppose that $G''$ has a visibility embedding. A visibility embedding $\xi$ of $G''$ that is also a canonical embedding
% is called a \emph{canonical visibility embedding} of $G''$.
We have the following lemma.
\begin{lemma} \label{canemb}
 If $G''$ is a PVG then every visibility embedding of $G''$ is a canonical visibility embedding.
\end{lemma}
\begin{proof}
We know from Lemmas \ref{4lp} and \ref{uemsgg} that $G$ has a unique visibility embedding. 
% We first show that adding vertices
% and edges to $G$ in order to construct $G''$ still allows only the unique visibility embedding when rest
% $\\ \\$
Let $\xi$ be the unique visibility embedding of $G$. Consider lines $L_1$, $L_2$, $L_3$ and $L_4$ in $\xi$ as before (Figure \ref{msgg}).
Note that $\vert L_3 \vert = \vert L_4 \vert = 2(20(m+n))^8$
Let $G''$ be a PVG and $\xi'$ be a visibility embedding of $G''$.
Observe that the total number of embedding points in $\xi' \setminus (L_1 \cup L_2 \cup L_2 \cup L_4)$
is less than $400(m+n)^2$. Moreover, the embedding points corresponding to the vertices of $G'$ 
are visible from most embedding points of $L_1$, $L_2$, $L_3$ and $L_4$. So, $G''$
satisfies the conditions of 
 Lemmas \ref{4lp} and \ref{uemsgg}, and by a similar argument, it can be shown that 
 the embedding points of $\xi'$ restricted to the vertices of $G$,
form the unique visibility embedding of $G$.
% $\\ \\$
%  Observe that the total number of vertices in $G'$ and $G''$ satisfies the conditions for 
%  Lemmas \ref{4lp} and \ref{uemsgg}, and the vertices and edges in $G'' \setminus G$
%  do not affect the arguments of these two lemmas. So, if $G''$ is a PVG and $\xi$
%  is a visibility embedding of $G''$ then 
%   the embedding points of $\xi$ restricted to the vertices of $G$,
% form the unique visibility embedding of $G$.
$\\ \\$
Now we show that every vertex $v_q \in G'$ satisfies the second condition of a canonical embedding.
Consider the embedding point $l^v_i \cap L_3$ in $\xi'$. Its corresponding vertex, by the construction of $G''$,
is not adjacent to $v_q$ if and only if $l^v_i$ is assigned as a coordinate to $v_q$.
A similar argument follows for $v_q$ and embedding points of the form $l^h_j \cap L_1$ in $\xi'$.
% Note that by the construction of $G''$,  $v_q$ is not adjacent to the vertex corresponding to the embedding point 
% $l^v_i \cap L_3$ (or, $l^h_j \cap L_1$) if and only if $l^v_i$ (respectively, $l^h_j$) is assigned as a coordinate to $v_q$.
% But an embedding point can lie on a horizontal or vertical line only when it is not 
% But 
On the other hand,
two non-consecutive embedding points on a horizontal or vertical line cannot be visible from each other.
So, 
% for all $v_q \in G'$, 
the embedding point of $v_q$  
is embedded on the intersection of horizontal and vertical lines 
% corresponding to 
giving 
a pair of coordinates
that has been 
assigned to $v_q$. Hence, $\xi'$ is a canonical visibility embedding of $G''$.
\end{proof}
\noindent 
% Let, as before, for $x_i$, 
Let us define the {variable pattern} of each $x_i$ and the {clause pattern} of each $C_j$.
For each $x_i$, let
$a = 400(m+n)^2 + n -  (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i}) 
 + 12m -1$,
%  6m + \sum _{k=1} ^{i-1} (2n_{k} +3 n_{\overline{k}} +6)$,
  $b =   2(20(m+n))^8 + \sum _{k=1} ^{i-1} (2n_{k} + 3\overline{n_{{k}}} +7)$,
  and $c=  \sum _{k=1} ^{i-1} (2n_{k} + 3\overline{n_{{k}}} + 3)$, as defined in Section \ref{subsecconsred}.
% $ \\ \\$
% 
% 
% 
% 
% 
% 
% 
For a canonical embedding $\xi$ of $G''$, the closed region bounded by the four lines 
 $l^v_{b+1}$,
 $l^v_{b+ 2n_{i} + 3\overline{n_{i}} +7}$,
  $L_3$
  and 
$l^h_{a+ 4n+c + 2n_{i} +2\overline{n_{i}} + 3 + \overline{n_i}}$
is called the \emph{variable pattern} of $x_i$ (Figure \ref{varpat}).
Let, for each $C_j$, let
$f = (\sum _{k=1} ^{n} (2n_{k} + 3n_{\overline{k}} +7)) + 12(j-1)$, as defined in Section \ref{subsecconsred}.
For a canonical embedding $\xi$ of $G''$,
the closed region bounded by the four lines 
$l^v_f$,
 $l^v_{f+12}$,
$L_3$
and 
$l^h_{400(m+n)^2}$
is called the \emph{clause pattern} of $C_j$ (Figure \ref{clpat}).
\begin{lemma} \label{satcan}
 If $\theta$ is not satisfiable, then $G''$ does not have a canonical visibility embedding.
\end{lemma}
\begin{proof}
 Assume on the contrary that $\theta$ is not satisfiable but $G''$ has a canonical visibility embedding $\xi'$. 
 So, each t-point of $\xi'$ is embedded on either its left o-line or right o-line. So, the embedding of the t-points
 corresponds to an assignment of $\theta$.
%  Wlog, suppose the assignment does not satisfy the clause $C_j$. This 
%  means that
 Since one of the clauses (say, $C_j$) is not satisfied, 
 the complements of the literals in $C_j$ have been assigned to $1$. Hence, if $l_{i,j} \in V^c_j$ 
 then $t_i$ lies on the left o-line of $x_i$ and $l_{i,j}$ must be embedded in the variable pattern of $x_i$ in $\xi'$.
 A similar argument holds if $\overline l_{i,j}$ is in $V^c_j$. This is true for all three literals of $C_j$. Hence,
 no l-point can be embedded in the clause pattern of $C_j$ in $\xi'$. Therefore, there is no embedding point 
 to block the visibility of the c-point from the second topmost embedding point of the c-line of $C_j$, 
 contradicting the assumption.
\end{proof}
% 
\begin{lemma} \label{redfrstdir}
 If $\theta$ is not satisfiable, then $G''$ is not a PVG.
\end{lemma}
\begin{proof}
 The proof follows from Lemmas \ref{canemb} and \ref{satcan}.
\end{proof}

\subsection{Reduction from 3-SAT}
% We have proved in Lemma \ref{redfrstdir} that if $\theta$ is not satisfiable then $G''$ is not a PVG.
% In Section \ref{propgnew} we have proved that if $\theta$ is not satisfiable then $G''$ is not a PVG.
In this Section we prove that if $\theta$ is satisfiable then $G''$ is a PVG.
Recall that if $\theta$ is not satisfiable then $G''$ is not a PVG.
% , hence completing the reduction.
%  In this part, we reduce the 3-SAT problem to the PVG recognition problem.
%  We have the following lemmas.
 We start by constructing a canonical embedding $\psi$ of $G''$,
 and then transform it into a canonical visibility embedding of $G''$.
%  where $\psi$ may not necessarily be a visibility embedding.
Let $S_\theta$ be a satisfying assignment of $\theta$.
%  We construct $\psi$ as follows.
 Since $G'' = G \cup G'$, 
%  \begin{enumerate} [(a)]
%   \item Embed 
  all the embedding points corresponding to the vertices of $G$ are embedded initially to form the unique visibility embedding of
  $G$. 
  Then, embedding points corresponding to $G'$ are embedded to complete the embedding $\psi$ of $G''$ (Figure \ref{3SAT})
  as follows.
  Repeat the following three steps for all $x_i \in \theta$.
   \begin{enumerate} [(a)]
  \item If $x_i$ is assigned $1$ in $S_ \phi$ then embed the t-point of $t_i$ on its left o-line. 
  Otherwise embed the t-point of $t_i$ on its right o-line.
%   Repeat this for all $x_i \in \theta$.
  \item If the t-point of $t_i$ is embedded on the its left o-line, then embed the d-point of $d_i$ on its right o-line.
  Otherwise embed the d-point of $d_i$ on its d-line.
%   Repeat this for all $x_i \in \theta$.
  \item If the t-point of $t_i$ is embedded on its left o-line, then embed the l-points of $l_{i,j}$
  on their first associated lines, for all $j$.
  Otherwise embed the l-points of $\overline l_{i,j}$
  on their first associated lines, for all $j$.
%   Repeat this for all $x_i$.
 \end{enumerate}

  \noindent 
%   Now, 
As a next step,
  for each clause $C_j$, choose an l-point of $C_j$ that has 
  not been embedded yet, and embed it on the intersection of the c-line
  and a horizontal line corresponding to a pair of coordinates assigned to its c-vertex.
  Observe that such l-points are always available for each clause, since $S_\theta$ is a satisfying assignment
  of $\theta$. All the remaining l-points are embedded on their second associated lines.
 The construction of $\psi$ is completed by the following step.
  \begin{enumerate} [(a)]
%  \item Embed all the remaining l-points on their second associated lines.
  \item Embed all the c-points and b-points on the intersection points representing the unique pair of coordinates assigned to them.
%   \item Adjust the horizontal and vertical lines so that each embedding point lies on no non-ordinary line other than its
%   vertical and horizontal lines.
 \end{enumerate}
 Now we need some definitions. A line passing through exactly two embedding points of $\psi$ is called an
 \emph{ordinary line}. A line passing through three or more embedding points of $\psi$ is called a
 \emph{non-ordinary line}.
Before the above embedding $\psi$ is transformed to a visibility embedding $\xi$ of $G''$,
we need the following lemma for rotating a line in $\psi$.
 \begin{lemma}
%  [rotating a single line] 
 \label{move1}
%  Suppose that $\psi$ is an embedding of $G''$.
 Consider a line $l'$ 
 of $\psi$. Let $\{ p_1, p_2, \ldots, p_q\}$ denote the order of all embedding points on $l'$
 where $p_i$ 
 lies on the intersection point of $l'$ and a non-ordinary line $l_i$  (Figure \ref{befig1}(a)).
%   $\{ l_1, l_2, \ldots, l_q\}$ be a set (possibly empty) of non-ordinary lines of $\psi$
%  such that each $p_i$   lies on the intersection point of $l'$ and $l_i$.
For any embedding point $p_j$ for $1 \leq j \leq q$, $l'$ can be rotated with $p_j$ 
as the pivot to form a new $l'$ satisfying the following properties.
% 
%   Let $\epsilon > 0$ be any positive real number. 
%  For any given $j$  such that $1 \leq j \leq q$,  it is always possible to re-embed $l'$
% %  while not changing the position of other vertical or horizontal lines in $\xi$ 
%  satisfying the following properties.
 \begin{enumerate}[(a)]
 \item \label{l1pa}
 The 
 embedding points of $\psi$ on $l'$, except $p_j$, are relocated on the new $l'$. All other embedding points in $\psi$ remain unchanged.
%  coordinates of all the vertices of $G''$ not embedded on $l'$ remain the same. 
%  \item The coordinates of $v_j$ remain the same.
% \item The embedding point $p_j$ is not moved.

\item \label{l1pd}
The order of embedding points on $l'$ and the new $l'$ are the same.
\item  \label{l1pc}
The order of embedding points on each $l_i$ also remains the same.
%  \item The order of embedding points on each $l_i$ remains the same.
%  \item The order in which the embedding points embedded on $l'$ occur on $l'$ remains the same.
%   \item $\forall i \neq j, 1 \leq i \leq p$, $v_i$ lies on $l_i$.
  \item  \label{l1pe}
  $\forall i \neq j, 1 \leq i \leq q$, $p_i$ does not lie on any other non-ordinary line.
  \item \label{l1pf}
  For each $p_i$ on $l'$, the Euclidean distance between the new and old positions of $p_i$ is less than  $\epsilon$.
 \end{enumerate}

 
\end{lemma}
\begin{proof} Rotate $l'$ with $p_j$ as the pivot in clockwise direction
 until it reaches a point $y$ on some line $l_i$ such that $y$ is either an intersection point of $\psi$ or 
 the length of the segment $p_iy$ is $\epsilon$.
%  
%  
%  
%  
%  $(i)$ $l'$ reaches an intersection point $y$ on some $l_i$, or $(ii)$ $l'$ reaches a point on some 
%  $l_i$ such that the length of the segment $p_iy$ is $\epsilon$. 
The new $l'$ is the line through 
 $p_j$ and 
%  $x$ where $x$ is 
 some point in the interior of $p_iy$.
 Embed each $p_i$ 
%  other than $p_j$, 
 on the intersection point of $l_i$ and the new $l'$ (Figure \ref{befig1}(b)).
 It can be seen that the properties (\ref{l1pa}), (\ref{l1pc}), (\ref{l1pd}), (\ref{l1pe}) and (\ref{l1pf})
 of the lemma are satisfied.
\end{proof}
\noindent 
Observe that in $\psi$, there can be several non-ordinary lines that are not horizontal or vertical lines.
The blocking relationships induced by these lines may not conform to the edges in $G'$.
% So, one by one, we consider 
Treating
each vertical line as $l'$ and each horizontal line
% passing through
intersecting
$l'$ as $l_i$,
% We repeat the
 Lemma \ref{move1} 
 is applied 
 on every vertical line in $\psi$.
%  to adjust the vertical lines
% %  
% %  Adjust the horizontal and vertical lines
%  such that 
%  Thus,
%  every embedding point now lies on no non-ordinary line other than its
%   vertical and horizontal lines.
  Thus, any non-ordinary line that now passes through an embedding point of $\psi$ is either a vertical or a horizontal line. 
%  $\\ \\$
%  In Section \ref{consalg} we have already constructed $G''$ in polynomial time.
% Now we first prove the forward direction of the theorem, i.e., $G''$ has a visibility embedding if $\theta$ has a satisfying assignment. We need the following lemmas. 
% % BASIC EMBEDDING LEMMAS.
%-------------------
We have the following lemma on rotating multiple lines of $\psi$.
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a55_f.pdf,width=0.900\hsize}}}
\caption{
(a) The lines $l_1, l_2, l_3, l_4$ and $l_5$ intersect $l'$
at $p_1$, $p_2$, $p_3$, $p_4$ and $p_5$ respectively. 
(b) The line $l'$ is rotated around $p_2$, 
so that all embedding points on $l'$
except $v_2$ are relocated. Each of the relocated embedding points lie on exactly two non-ordinary lines and within
$\epsilon$ distance of their previous positions.
}
\label{befig1}
\end{center}
\end{figure}
\begin{lemma} 
% [re-embedding given points on a line] 
\label{move3}
%   Suppose that $\xi$ is an embedding of $G''$. 
  Consider a vertical line $l'$ 
 of $\psi$. 
 Let $( w_i, w_{i+1}, \ldots, w_{i+j-1}, w_{i+j} )$ be all embedding points on $l'$ from $w_i$ to $w_{i+j}$
 such that they lie on the intersection points of $l'$ with $( l_i, l_{i+1}, \ldots, l_{i+j-1}, l_{i+j})$ respectively.
%  
%  
%  
%  Let $( w_i, w_{i+1}, \ldots, w_{i+j-1}, w_{i+j} )$ be consecutive embedding points of $\psi$ on $l'$
%  in the top to bottom order that are lying on the intersection points of $l'$ with horizontal lines 
%  $( l_i, l_{i+1}, \ldots, l_{i+j-1}, l_{i+j} )$.
% %  Additionally, suppose that the embedding points on the horizontal
% %  lines passing through $( v_i, v_{i+1}, \ldots, v_{j-1}, v_j )$ lie on no non-ordinary lines
% %  except vertical and horizontal lines. 
 Let $q_1$ and $q_2$ be any two designated points on the interval
 $w_{i+1}w_{i+j-1}$. 
%  Then 
 For every line $l_{i+k} \in ( l_{i+1}, \ldots, l_{i+j-1})$, a new $l_{i+k}$ can be constructed such that 
 $l_{i+k}$ intersects $l'$ at a point $r_{k}$ satisfying the following properties.
  \begin{enumerate}[(a)]
  \item \label{l2pa}
  The points $( r_1, r_2, \ldots, r_{i+j-1} )$ lie
  on $q_1q_2$ and their order follows the order of 
  $( w_i, w_{i+1}, \ldots, w_{i+j-1}, w_{i+j} )$.
%   in the same order of corresponding horizontal lines,
%   in the interior of the interval $q_1q_2$.
%   
%    \item The embedding points $ w_{i+1}, \ldots, w_{j-1}$ are embedded on the points 
%     $p_1, p_2, \ldots, p_{i+j-2}$ respectively. 
   \item  \label{l2pb}
   The non-ordinary lines passing through the embedding points on 
   $( l_i, l_{i+1}, \ldots, l_{i+j-1}, l_{i+j} )$ are either vertical or horizontal lines.
%    
%    No embedding point on these horizontal lines lies on a non-ordinary line 
%    that is not a vertical or horizontal line.
  \end{enumerate}

\end{lemma}
\begin{proof} 
Let $p'_1$ be a point on $q_1q_2$. 
Set $\epsilon = \frac{1}{2} min (q_1r'_1, r'_1q_2)$
Rotate the line passing through $r'_1$ and $p_1$ with 
% $\epsilon = \frac{1}{2} min (q_1r'_1, r'_1q_2)$ and 
$p_1$ as the pivot
using Lemma \ref{move1} to obtain a new intersection point $r_1$ on $l'$. The line passing through $p_1$ and 
$r_1$ is the new $l_1$, and embedding points on $l_1$ are relocated on the corresponding intersection points of 
the new $l_1$.
Analogously, choose a point $r'_2$ on $r_1q_2$ and construct the new $l_2$ giving a new intersection point 
$r_2$ of $l'$ on $r_1q_2$.
These operations are performed on all lines in $( l_{i+1}, \ldots, l_{i+j-1})$. 
It can be seen that the properties (\ref{l2pa}) and (\ref{l2pb})
 of the lemma are satisfied.
\end{proof}
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a54_f.pdf,width=0.900\hsize}}}
\caption{
(a) The b-points $b_1$, $b_2$, $b_3$ and $b_4$ lie in the interior of the quadrilateral $q_1q_2q_3q_4$.
(b) The b-points $b_1$, $b_2$, $b_{3}$ and $b_4$ are relocated inside $q_1q_5q_6q_4$,
with $b_1$ blocking the segment $a_4c_4$. 
% The new positions of $p_{11}$ and $p_4$ are coloured in pink.
}
\label{befig2}
\end{center}
\end{figure}

$\\ \\$
Using Lemma \ref{move3}, we show that embedding points inside a special type of quadrilateral can be relocated 
as blockers of pairs of embedding points lying outside the quadrilateral.
Consider a quadrilateral $Q = (q_1, q_2, q_3, q_4)$, where $q_1$, $q_2$, $q_3$ and $q_4$
are embedding points of $\psi$ lying on 
$(l^v_{x_1},l^h_{y_1})$,
$(l^v_{x_1},l^h_{y_2})$, $(l^v_{x_2},l^h_{y_2})$ and $(l^v_{x_2},l^h_{y_1})$ respectively,
and $x_1<x_2$ and $y_1<y_2$.
Let $B$
% = \{ b_1, b_2, \ldots, b_k \}$
be the set of all embedding points lying inside $Q$.
% $\\$
$B$ is said to be an \emph{ordered set} if no two embedding points of $B$ lie on the same horizontal or 
vertical line, and $B$ satisfies exactly one of the following properties.
\begin{enumerate}
 \item For all embedding points $b' \in B$ and $b'' \in B$ embedded on $(l^v_{x'},l^h_{y'})$ and $(l^v_{x''},l^h_{y''})$ respectively,
%  $(i)$ $x' \neq x''$, $(ii)$ $y' \neq y''$, and $(iii)$ 
%  if 
   $x'<x''$ (or, $x'>x''$) then $y'<y''$ (respectively, $y'>y''$).
   \item For all embedding points $b' \in B$ and $b'' \in B$ embedded on $(l^v_{x'},l^h_{y'})$ and $(l^v_{x''},l^h_{y''})$ respectively,
%  $(i)$ $x' \neq x''$, $(ii)$ $y' \neq y''$, and $(iii)$ 
%  if 
   $x'<x''$ (or, $x'>x''$) then $y'>y''$ (respectively, $y'<y''$).
   
   
   
\end{enumerate}

$\\ $
Let $A$
% = \{ a_1, a_2, \ldots, a_k \}$ 
be a set of embedding points of $\psi$ such that 
each $a_i \in A$ lies to the left of $l^v_{x_1}$ and also lies either above $l^h_{y_1}$ or below $l^h_{y_2}$.
% Let $B = \{ a_1, a_2, \ldots, a_k \}$ be the set of all the embedding points lying inside $Q$.
Let $C$ 
% = \{ c_1, c_2, \ldots, c_k \}$
be a set of embedding points of $\psi$ such that 
each $c_i \in C$ lies to the right of $l^v_{x_2}$ and  also lies either above $l^h_{y_1}$ or below $l^h_{y_2}$.
% Additionally, let $Q$, $A$, $B$ and $C$ satisfy the following three properties.
Let $S$
% \subseteq A \times C$ 
be a set of line segments $a_ic_j$ where $a_i \in A$ and $c_j \in C$,
and $a_ic_j$ intersects both $q_1q_4$ and $q_2q_3$. 
A pentuple $U = (Q,A,B,C,S)$ is called a \emph{good pentuple} if 
% it satisfies the following properties.
% \begin{enumerate}[(a)]
% \item 
$ \vert B \vert \geq \vert S \vert $, and
   $B$ is an ordered set.
\begin{lemma} 
 \label{mainmovelem1}
 For a given good pentuple $U = (Q,A,B,C,S)$ in $\psi$, horizontal and vertical lines passing through 
 the embedding points of $B$ can be relocated satisfying the following properties.
  \begin{enumerate}[(a)]
  \item All horizontal and vertical lines in $\psi$ retain their angular ordering around $p_1$ and $p_2$ respectively.
   \item Each embedding point in $B$ lies on exactly one segment of $S$.
   \item Each embedding point in $B$ lies on exactly three non-ordinary lines, two of which are horizontal and vertical lines.
   \item 
   For every horizontal or vertical line $l''$ containing $b \in B$, no embedding point on 
   $l'' \setminus \{ b \}$ lies on a third non ordinary line after relocation.
%    All other embedding points on the new vertical and horizontal lines containing the elements of $B$ 
%    lie on exactly two non-ordinary lines, i.e. the vertical and horizontal lines containing them. 
%    Furthermore, all the embedding points on the horizontal and vertical lines containing these vertices lie on 
%    exactly two non-ordinary lines i.e., their corresponding vertical and horizontal lines. 
  \end{enumerate}
\end{lemma}
\begin{proof}
% We prove this lemma by induction on $ \vert S \vert$, where the base case is the trivial case with $S$ as the empty set. Let 
% $ \vert S \vert = k$ and the lemma be true for all good pentuples with smaller values of $ \vert S \vert = k$.
Wlog let $S$ satisfy Property $1$ of ordered sets. Choose an appropriate point $q_5 \in q_1q_2$ 
such that no intersecting points of the segments of $S$ lie
in the interior of $q_1q_5q_6q_4$, where $q_6$ is the point of intersection of $p_1q_5$ and $q_3q_4$
(Figure \ref{befig2}(a)).
Let $H_Q$ and $V_Q$ be the set of all horizontal and vertical lines passing through $Q$, respectively.
By applying Lemma \ref{move3} on any vertical line in $V_Q$, relocate all horizontal lines
of $H_Q$ such that all of them pass through $q_1q_5q_6q_4$.
$\\ \\$
Observe that all embedding points of $B$ have moved inside $q_1q_5q_6q_4$.
% .,
% so that they can be relocated 
% % and they have to be placed 
% on the segments of $S$ as blockers.
% $\\ \\$
Since none of the segments of 
$S$ intersect inside $q_1q_5q_6q_4$, they have a left to right order defined by their intercepts on $q_5q_6$.
Let $a_ic_j$ be the leftmost segment of $S$ in this order.
Denote the leftmost embedding point of $B$ as $b$, and let $l^v_x$ and $l^h_y$ be its vertical and horizontal lines 
respectively.
Applying Lemma \ref{move3} on any horizontal line in $H_Q$, all vertical lines 
of $V_Q$ are relocated such that $l^v_x$ intersects $a_ic_j$ at a point (say, $p$) (Figure \ref{befig2}(b)),
maintaining other lines of $V_Q$ passing through $q_1q_5q_6q_4$.
Treating $p$ as an embedding point and taking $p_2$ as the pivot, Lemma \ref{move1} can be applied on
$l^v_x$ to ensure that $p$ does not lie on any other non-ordinary line.
% Assume that $p$ is an embedding point, and rotate $l^v_x$ by applying Lemma \ref{move1}.
% % Note that $p$ does not lie on any ordinary line other than $l^v_x$ and $
Now embed $b$ on $p$ by relocating $l^h_y$ accordingly.
% such that it passes through $p$, relocating $b$ on $p$, 
% and 
Relocate all other horizontal lines
of $H_Q$ by applying Lemma \ref{move3}, maintaining all lines of $H_Q$ passing through $q_1q_5q_6q_4$.
$\\ \\$
It can be seen that $U' = (bq_7q_3q_8,A,B \setminus \{ b \},C,S \setminus \{ a_ic_j \} )$ is a good pentuple, 
where $q_7 = l^v_x \cap q_5q_6$
 and $q_8 = l^h_y \cap q_3q_4$.
 Repeating the above procedure, 
%  we can eventually block 
%  all segments of $S$ using 
 embedding points of $B$
%  ,
 are placed on all segments of $S$ as blockers,
 satisfying  properties (a), (b), (c) and (d) of the lemma.
 Analogous arguments of the proof are applicable if $B$ satisfies Property $2$ of ordered sets.
\end{proof}
$\\$
Now we use Lemmas \ref{move1}, \ref{move3} and \ref{mainmovelem1} to finally transform $\psi$ into a 
visibility embedding $\xi$ of $G''$. We have the following lemma.
\begin{figure}
\begin{center} 
\centerline{\hbox{\psfig{figure=a52_f.pdf,width=0.990\hsize}}}
\caption{(a)
Since t-point lies on the left o-line, blockers are placed between t-point and right o-points.
% Modification of $\psi$ when the t-point is on the left o-line.
The quadrilateral required for a good pentuple is 
shaded in gray.
(b)
Since t-point lies on the right o-line, blockers are placed between t-point and left o-points.
Since b-point lies on the d-line, blockers are placed between d-point and right o-points.
% Modification of $\psi$ when the t-point is on the right o-line. 
Quadrilaterals required for a good pentuple are
shaded in gray.
}
\label{embex}
\end{center}
\end{figure}
\begin{lemma} \label{mainmovelem2}
 The canonical embedding $\psi$ can be transformed into a visibility embedding  $\xi$ of $G''$.
\end{lemma}
\begin{proof}
 The only adjacency relationships of $G''$ that $\psi$ may not satisfy are those $(i)$ between o-vertices and t-vertices,
 $(ii)$ between o-vertices and d-vertices, and $(iii)$ between t-vertices, l-vertices, 
 d-vertices and vertices corresponding to certain points
 on $L_3$.
%  Our strategy is to identify suitable good pentuples in $\psi$ and relocate lines to satisfy all these 
%  adjacency relationships. In the proof, we identify suitable quadrilaterals for groups of segments to be blocked,
%  and the corresponding good pentuples naturally follow from each such quadrilateral.
%  $\\ \\$
Consider $(i)$ and $(ii)$.
 For each $x_i$, if the t-point of $t_i$ is embedded on its left o-line, then consider the quadrilateral $Q$ 
 formed by the horizontal line passing through the topmost right o-point, horizontal line of the t-point,
 left o-line and right o-line. Draw two more vertical and horizontal lines such that they form a quadrilateral $Q'$ 
 in the interior of $Q$, and only nominally smaller than $Q$. It can be seen that $Q'$, $t_i$, the right o-points,
 the l-points of the form $\overline l_{i,j}$, and all segments between the t-point and the right o-points
 form a good pentuple. Hence these segments can be blocked by relocating the corresponding l-points using Lemma 
 \ref{mainmovelem1} (Figure \ref{embex} (a)).
 A similar argument works if the t-point is embedded on the right o-line (Figure \ref{embex} (b)), or if the d-point is embedded
 on the d-line (Figure \ref{embex} (b)).
 $\\ \\$
 Consider $(iii)$.
%  All the other segments of $\psi$ that are to be blocked have an end point on $L_3$. 
 Let $S_L$ be all such segments having an endpoint on $L_3$ (\ref{3SAT}).
%  Let $S_L$ be the set of all such line segments.
%  Construct a horizontal line $l^h_y$ through $p_1$ such that $l^h_y$ is below $L_3$ but the intersection points of every segment of $S_L$  
%  with $\psi \setminus {L_4}$ are below $l^h_y$.
 Locate a point $p_3$ on $l^h_1$ such that 
%  embedding points of $L_3$ are above ${p_1p_3}$,
 $L_3$ and $L_4$ are above and below $p_1p_3$ respectively.
Moreover, the intersection points of $S_L$ with vertical lines of $\psi \setminus \{L_3 \}$ lie below $p_1p_3$.
%  but  the intersection points of every segment of $S_L$  
%  with $\psi \setminus {L_4}$ are below ${p_1p_3}$.
 Let $H_L$ be the set of all horizontal lines between $L_3$ and $l^h_{a+4n+1}$,
 where $a = 400(m+n)^2 + n -  (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i}) 
 + 12m - 1$  as stated in Section \ref{subsecconsred}.
 Apply lemma \ref{move3} on any vertical line of $\psi$, and treating its intersection points with horizontal lines as embedding points, 
 all horizontal lines of $H_L$ are relocated
 so that they are above 
 ${p_1p_3}$.
%  where $a = 400(m+n)^2 + n -  (8n + 18m + \sum\limits_{x_i \in \theta}\overline{n_i}) 
%  + 12m - 1$  as stated in Section \ref{subsecconsred}.
  Consider any segment $s_j \in S_L$. Let the two endpoints of $s_j$ in $\psi$ be $r_1(s_j)$ and $r_2(s_j)$, where $r_1(s_j) \in L_3$. Let the 
  two vertical lines passing through $r_1(s_j)$ and $r_2(s_j)$ be $l^v_{u_j}$ and $l^v_{w_j}$ respectively. Observe that if 
  $u_j < w_j$ (or, $u_j > w_j$) then $l^v_{u_j+1}$ (respectively, $l^v_{u_j-1}$) contains a b-point lying on a horizontal line of $H_L$,
  due to the construction of $\psi$.
 Such a b-point exists for every segment in $S_L$.
 For two segments of $S_L$ with a common endpoint on a c-line, the two b-points on the two vertical lines immediately to the left of the c-line 
 correspond to the two segments.
 Let $B_L$ denote the set of all these b-points.
%  Let $B_L$ be the set of all such b-points, each corresponding to a segment in $S_L$.
Now consider a b-point $b_i \in B_L$ such that the horizontal line passing through $b_i$ (say, $l^h_{y_i}$) is lower than the 
horizontal line passing through any other b-point of $B_L$.
$ \\ \\$
Let $s_i \in S_L$ be the segment corresponding to $b_i$. 
% The embedding point on $s_i \cap L_3$ may be the endpoint of $(a)$ only $s_i$, or $(b)$ $s_i$ and another segment of $s_i$.
% $ \\ \\$
% Consider $(a)$.
% Wlog suppose $u_i < w_i$. 
Let $Q_i$ be the quadrilateral enclosed by $l^v_{u_i}$, $l^v_{u_{i+2}}$, ${p_1p_3}$
and $l^h_{y_i -1}$, assuming $u_i < w_i$. 
Observe that $Q_i$, $B_i = \{ b_i \}$, $A_i = \{r_1(s_i) \}$, $C_i = \{r_2(s_i) \}$ and $S_i = \{ s_i \}$
constitute a good pentuple, say, $U_i$. Apply Lemma \ref{mainmovelem1} on $U_i$ to place $b_i$ as a blocker on $s_i$.
% Note that since there no other embedding point on the horizontal and vertical lines passing through $b_i$ corresponds to any vertex of $G'$,
% none of the already constructed blocking relationships are disturbed.
Remove $b_i$ and $s_i$ from $B_L$ and $S_L$ respectively. Remove $l^h_{y_i}$ and all horizontal lines below it from $H_L$.
Repeat the process on the lowest b-point of $B_L$, 
treating $l^h_{y_i}$ as the new $p_1p_3$.
% Consider $l^h_{y_i}$ as the next $p_1p_3$. 
% Shift $p_3$ on $l^h_1$ such that
% $b_i$ lies below ${p_1p_3}$ but the  
%  remaining horizontal lines of $H_L$ lie above ${p_1p_3}$. 
% Consider $(b)$.
$\\ \\$
It may so happen that the same embedding point on $L_3$ is the endpoint of two segments $s_i$ and $s_j$ in $S_L$,
i.e., $r_1(s_i) = r_1(s_j)$.
This case arises only when 
% In this case,
% When the 
% this common 
$r_1(s_i)$ and $r_1(s_j)$
% endpoint of $s_i$ and $s_j$ lies
lie
on a c-line of $\psi$.
% , it is the endpoint of another segment $s_j \in S_L$.
In this case, the two b-points on the two vertical lines immediately to the left of the c-line are relocated
as blockers on $s_i$ and $s_j$, using an analogous process.
% It can be seen that an analogous argument is applicable, with two b-points instead of one b-point being relocated inside
% the quadrilateral.
$\\ \\$
Hence, b-points can be assigned as blockers on segments of $S_L$ in cases $(i)$, $(ii)$ and $(iii)$. Therefore,
% Hence, 
the canonical embedding $\psi$ can be transformed into a visibility embedding  $\xi$ of $G''$.
% Repeating the above procedure, all the segments of $S_L$ can be blocked using b-points of $B_L$, transforming 
% $\psi$ into a visibility embedding $\xi$ of $G''$.
\end{proof}
$\\$
Finally, we have the following theorem.
\begin{theorem}
 The recognition problem for PVGs in NP-hard.
\end{theorem}
\begin{proof}
 Given a 3-SAT formula $\theta$, the construction of the corresponding graph $G''$ takes polynomial time, due to Lemma \ref{polytime}.
 The graph $G''$ is a PVG if and only if $\theta$ is satisfiable, due to Lemma \ref{redfrstdir} and Lemma \ref{mainmovelem2}.
 Hence the recognition problem for PVGs in NP-hard.
\end{proof}
\begin{cor}
 The reconstruction problem for PVGs in NP-hard.
\end{cor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  HARDNESS OF APPROXIMATION  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


\section{Concluding remarks} \label{conclrem}
In this paper we have proved that
% if a graph is a PVG, then there it has a visibility where all the coordinates
% of its vertices are rational. We have also proved that
the recognition and reconstruction problems for point visibility graphs, are
NP-hard. 
On the other hand, we know that the recognition problem for point visibility graphs is in PSPACE \cite{recogpvg-2014}.
So it will be interesting see if the problem is in NP, which is mentioned as \emph{Open Problem 4} in 
 \cite{prob-ghosh}.
% However, these results do not imply that the recognition or reconstruction problems are in NP.
% The classification of these two problems remains unsolved.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  ACKNOWLEDGEMENTS  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Acknowledgements} 
The author would like to thank Jean-Lou De Carufel,
Anil Maheshwari and Michiel Smid for the many discussions that 
helped to structure the paper.
The author would also like to thank Amitava Bhattacharya,  
and Prahladh Harsha for their valuable suggestions. 
The author is specially thankful to Subir Kumar Ghosh 
 for his suggestions which have improved the presentation of the paper significantly.
\bibliographystyle{plain}
\bibliography{vis}
\end{document}


final_draft2.bbl
\begin{thebibliography}{10}

\bibitem{cgl-pgd-85}
B.~Chazelle, L.~J. Guibas, and D.T. Lee.
\newblock The power of geometric duality.
\newblock {\em BIT}, 25:76--90, 1985.

\bibitem{bcko-cgaa-08}
M.~de\ Berg, O.~Cheong, M.~Kreveld, and M.~Overmars.
\newblock {\em Computational Geometry, Algorithms and Applications}.
\newblock Springer-Verlag, 3rd edition, 2008.

\bibitem{diestel}
R.~Diestel.
\newblock {\em Graph Theory}.
\newblock Springer-Verlag, 2005.

\bibitem{Edelsbrunner:1986:CAL}
H.~Edelsbrunner, J.~O'Rourke, and R.~Seidel.
\newblock Constructing arrangements of lines and hyperplanes with applications.
\newblock {\em SIAM Journal on Computing}, 15:341--363, 1986.

\bibitem{g-vap-07}
S.~K. Ghosh.
\newblock {\em Visibility Algorithms in the Plane}.
\newblock Cambridge University Press, 2007.

\bibitem{prob-ghosh}
S.~K. Ghosh and P.~P. Goswami.
\newblock Unsolved problems in visibility graphs of points, segments and
  polygons.
\newblock {\em ACM Computing Surveys}, 46(2):22:1--22:29, December, 2013.

\bibitem{recogpvg-2014}
S.~K. Ghosh and B.~Roy.
\newblock Some results on point visibility graphs.
\newblock In {\em Proceedings of the Eighth International Workshop on
  Algorithms and Computation}, volume 8344 of {\em Lecture Notes in Computer
  Science}, pages 163--175. Springer-Verlag, 2014.

\bibitem{kpw-ocnv-2005}
J.~K\'ara, A.~P{\'o}r, and D.~R. Wood.
\newblock {On the Chromatic Number of the Visibility Graph of a Set of Points
  in the Plane}.
\newblock {\em Discrete \& Computational Geometry}, 34(3):497--506, 2005.

\bibitem{lw-apcf-79}
T.~Lozano-Perez and M.~A. Wesley.
\newblock An algorithm for planning collision-free paths among polyhedral
  obstacles.
\newblock {\em Communications of ACM}, 22:560--570, 1979.

\bibitem{viscon-wood-2012}
M.~S. Payne, A.~P{\'o}r, P.~Valtr, and D.~R. Wood.
\newblock On the connectivity of visibility graphs.
\newblock {\em Discrete \& Computational Geometry}, 48(3):669--681, 2012.

\bibitem{p-vgps-2008}
F.~Pfender.
\newblock Visibility graphs of point sets in the plane.
\newblock {\em Discrete \& Computational Geometry}, 39(1):455--459, 2008.

\bibitem{sh-ddsg-79}
L.G. Shapiro and R.M. Haralick.
\newblock Decomposition of two-dimensional shape by graph-theoretic clustering.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  PAMI-1:10--19, 1979.

\end{thebibliography}
