\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{mathrsfs,pstricks,ifpdf,tikz}
%\usepackage[colorlinks,linkcolor=red,anchorcolor=blue,citecolor=green]{hyperref}
\usepackage{amsfonts}
\usepackage{enumerate}
%\topmargin 0 pt \textheight 46\baselineskip \advance\textheight by \topskip
%\setlength{\parindent}{16pt}
%\setlength{\parskip}{3pt plus 1pt minus 1pt} %%
%\setlength{\textwidth}{145mm}
%\setlength{\oddsidemargin}{5.6mm} \setlength{\evensidemargin}{5.6mm}
\usepackage{makecell}
%\newcommand{\bahao}{\fontsize{6pt}{\baselineskip}\selectfont}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}
\usepackage{latexsym}
\usepackage{amsmath,amssymb}
\usepackage{amsthm}
\usepackage{ifthen,calc}
\usepackage{color}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{multirow}
\usepackage{diagbox}
\usepackage{float}
\usepackage[format=hang, margin=10pt]{caption}
%\newtheorem*{theorem}{定理}%定理不编号命令
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{property}[theorem]{Property}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{notation}[theorem]{Notation}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newcommand{\qihao}{\fontsize{7.5pt}{\baselineskip}\selectfont}%%%%%%字体大小
\newcommand{\ssum} {\sum_{i=1}^{\infty} }
\def\dsum{\displaystyle\sum}
\def\rs{\rm\scriptsize}
\newcommand{\mdef}[1]{\textit{\textbf{#1}}} %%JG
\newcommand{\vsa}{\vskip-12pt}
\newcommand{\vsb}{\vskip-6pt}
\newcommand{\Z}{{\mathbb Z}}
%\newcounter{hours}
%\newcounter{minutes}
%\newcommand{\printtime}{
% \setcounter{hours}{\time/60}%
% \setcounter{minutes}{\time-\value{hours}*60}
% \ifthenelse{\value{hours}<10}{0}{}\thehours:%
% \ifthenelse{\value{minutes}<10}{0}{}\theminutes}
\def\CL#1{\left\lceil#1\right\rceil}
\def\FL#1{\left\lfloor#1\right\rfloor}
\def\VEC#1#2#3{#1_{#2},\ldots,#1_{#3}}
\def\UM#1#2{\bigcup_{{#1}\in{#2}}}
\def\FR#1#2{\frac{#1}{#2}}
\def\NN{{\mathbb N}}
\def\C#1{\left\vert{#1}\right\vert}
\def\wG{{\widehat G}}
\renewcommand{\baselinestretch}{1.15}
\begin{document}
\title{On the bar visibility number of complete bipartite graphs}
\author{
Weiting Cao\thanks{University of Illinois, Urbana, USA: caoweiting@gmail.com.}\,
\qquad
Douglas B. West\thanks{Zhejiang Normal University, Jinhua, China, and
University of Illinois, Urbana, USA: dwest@math.uiuc.edu.
Supported by NNSF of China under Grant NSFC-11871439.}
\qquad
Yan Yang\thanks{Tianjin University, Tianjin, China: yanyang@tju.edu.cn.
Supported by NNSF of China under Grant NSFC-11401430.}\,
}
\date{\today}
\maketitle
\begin{abstract}
A {\it $t$-bar visibility representation} of a graph assigns each vertex up to
$t$ horizontal bars in the plane so that two vertices are adjacent if and only
if some bar for one vertex can see some bar for the other via an unobstructed
vertical channel of positive width. The least $t$ such that $G$ has a $t$-bar
visibility representation is the {\it bar visibility number} of $G$, denoted by
$b(G)$. For the complete bipartite graph $K_{m,n}$, the lower bound
$b(K_{m,n})\ge\lceil{\frac{mn+4}{2m+2n}}\rceil$ from Euler's Formula is
well known. We prove that equality holds.\\
\noindent
Keywords: bar visibility number; bar visibility graph; planar graph; thickness;
complete bipartite graph.
\noindent
MSC Codes: {05C62, 05C10}
\end{abstract}
\section{Introduction}
In computational geometry, graphs are used to model visibility relations in the
plane. For example, we may say that two vertices of a polygon ``see'' each
other if the segment joining them lies inside the polygon. In the
{\it visibility graph} on the vertex set, vertices are adjacent if they see
each other. More complicated notions of visibility have been defined for
families of rectangles and other geometric objects. Dozens of papers
have been written concerning construction and recognition of visibility
graphs and applications to search problems and motion planning. For a textbook
on algorithms for visibility problems, see Ghosh~\cite{Gho}.
We consider visibility among horizontal segments in the plane. A graph $G$ is
a \textit{bar visibility graph} if each vertex can be assigned a horizontal
line segment in the plane (called a {\it bar}) so that vertices are adjacent if
and only if the corresponding bars can see each other along an unobstructed
vertical channel with positive width. The assignment of bars is a
\textit{bar visibility representation} of $G$. The condition on positive width
allows bars $[(a,y),(x,y)]$ and $[(x,z),(c,z)]$ to block visibility at $x$
without seeing each other.
Tomassia and Tollis~\cite{Tamassia86} and Wismath~\cite{Wismath85} found a
simple characterization of bar visibility graphs. Hutchinson~\cite{Hut}
later gave another simple proof for the $2$-connected case.
\begin{theorem}[\cite{Tamassia86, Wismath85}]\label{4}
A graph $G$ has a bar visibility representation if and only if for some
planar embedding of $G$ all cut-vertices appear on the boundary of one face.
\end{theorem}
Theorem~\ref{4} is quite restrictive. Nevertheless, assigning multiple bars to
vertices permits representations of all graphs and leads to a complexity
parameter measuring how many bars are needed per vertex, introduced by Chang,
Hutchinson, Jacobson, Lehel, and West \cite{Chang04}.
%(Axenovich, Beveridge, Hutchinson, and West~\cite{ABHW} introduced an analogue
%for directed graphs.)
\begin{definition}[\cite{Chang04}]
A \emph{$t$-bar visibility representation} of a graph assigns to each vertex
at most $t$ horizontal bars in the plane so that vertices are adjacent if and
only if some bar assigned to one sees some bar assigned to the other via
an unobstructed vertical channel of positive width.
The \emph{bar visibility number} of a graph $G$, denoted by $b(G)$, is the
least integer $t$ such that $G$ has a $t$-bar visibility representation.
\end{definition}
%More precisely, given a graph $G$, suppose that each vertex $u$ is assigned a
%set $S_u$ of at most $t$ horizontal bars. Suppose also that vertices $u$ and
%$v$ are adjacent if and only if some bar from $S_u$ and some bar from $S_v$ can
%``see" each other via an unobstructed vertical line segment with positive
%width.
Results in \cite{Chang04} include the determination of visibility number for
planar graphs (always at most $2$), plus $b(K_n)=\CL{n/6}$ for $n\ge7$, the
determination of $b(K_{m,n})$ within $1$, and $b(G)\le \CL{n/6}+2$
for every $n$-vertex graph $G$. Results on the visibility numbers for
hypercubes~\cite{West17} and an analogue for directed graphs~\cite{ABHW} have
also been obtained. For complete bipartite graphs, the result was as follows.
\begin{theorem}[\cite{Chang04}]\label{1}
$r\leq b(K_{m,n})\leq r+1$, where $r=\CL{\frac{mn+4}{2m+2n}}$.
\end{theorem}
\noindent
To prove the lower bound, consider a $t$-bar representation, add edges to
encode visibilities that produce edges of $K_{m,n}$, and then shrink bars to
single points. This produces a bipartite plane graph $H$ with at most $t(m+n)$
vertices and at least $mn$ edges. Hence $mn\le 2t(m+n)-4$ by Euler's Formula,
so $b(K_{m,n})\ge r$. Equality requires most faces in $H$ to have length $4$.
In this paper, we prove $b(K_{m,n})=r$. Section $2$ contains a short proof
valid for $K_{n,n}$. For this case, it suffices to decompose the graph into
$r$ bar visibility graphs, where a \textit{decomposition} of $G$ is a set of
edge-disjoint subgraphs whose union is $G$. The subgraphs can then be
repesented with disjoint projections on the horizontal axis. In Section $3$,
we present a different approach that solves the problem for all complete
bipartite graphs.
Our results are related to earlier work. A {\it $t$-split} of a graph $G$ is a
graph $H$ in which each vertex is replaced by a set of at most $t$ independent
vertices in such a way that $u$ and $v$ are adjacent in $G$ if and only if some
vertex in the set representing $u$ is adjacent in $H$ to some vertex in the set
representing $v$. The graph $G$ used to prove the lower bound for
Lemma~\ref{1} is an example of a $t$-split of $K_{m,n}$. As defined by
Eppstein et al.~\cite{Epp}, the {\it planar splitting thickness}
(or simply {\it split thickness}) of a graph $G$, which we denote by
$\sigma(G)$, is the minimum $t$ such that $G$ has a $t$-split that is a
planar graph. As explained above, always $\sigma(G)\le b(G)$. If $G$ has
a $\sigma(G)$-split that is $2$-connected, then $\sigma(G)=b(G)$.
This connection was noted earlier in the thesis of the first author~\cite{Cao},
where planar split thickness was given the unfortunate name ``split number'',
creating confusion with another concept. The {\it splitting number} of a
graph is the minimum number of successive splits of one vertex into two
(with each incident edge being inherited by one of the two new vertices)
needed to produce a planar graph.
The notion of $t$-split originated with Heawood~\cite{Hea}, who proved
that $K_{12}$ has a $2$-split. Later, Ringel and Jackson~\cite{RJ}
proved in effect that $K_n$ has a $\CL{n/6}$-split. A short proof of this
by Wessel~\cite{Wes} was used in~\cite{Chang04} to prove $b(K_n)=\CL{n/6}$.
The results in~\cite{Epp} that concern complete bipartite graphs determine
those that are $2$-splittable. They are the same as those having bar
visibility number at most $2$. Their lower bounds on $\sigma(K_{m,n})$ use
the same counting argument from Euler's Formula that yields the lower bounds
for $b(K_{m,n})$ (see~\cite{Chang04}).
In~\cite{Epp}, the authors close the paper by asking whether graphs embeddable
on the surface of genus $k$ are $(k+1)$-splittable, as an open question.
This follows from a recent result about the {\it thickness} $\theta(G)$ of a
graph $G$, defined to be the minimum number of planar graphs needed to
decompose $G$. A decomposition into $k$ planar graphs is a $k$-split,
so $\sigma(G)\le \theta(G)$; this motivates the term ``split thickness''.
Xu and Zha~\cite{XZ} proved that $\theta(G)\le k+1$ when $G$ embeds on the
surface of genus $k$, thereby providing a positive answer to the question
in~\cite{Epp}.
\section{The bar visibility number of $K_{n,n}$}
As noted above, thickness provides an upper bound on the split number,
and the split number usually equals the bar visibility number. Beineke,
Harary, and Moon~\cite{BHM64} determined $\theta(K_{m,n})$ for most $m$ and $n$.
\begin{lemma}[\cite{BHM64}]\label{3a}
$\theta(K_{n,n})=\CL{\frac{n+2}{4}}$.
\end{lemma}
When $\theta(K_{n,n})$ is the desired value for $b(K_{n,n})$, we aim to
decompose $K_{n,n}$ into that number of bar visibility graphs. The difficult
case is when $b(K_{n,n})<\theta(K_{n,n})$.
\begin{theorem}\label{2}
$b(K_{n,n})=\CL{\frac{n+1}{4}}$, except for $b(K_{3,3})=2$.
\end{theorem}
\begin{proof}
It is immediate that $K_{1,1}$ and $K_{2,2}$ are bar visibility graphs.
Since $K_{3,3}$ is not planar, $b(K_{3,3})\ge 2$; equality holds because
$K_{3,3}$ decomposes into a $6$-cycle and a matching of size $3$, both of
which are bar visibility graphs. Hence we may assume $n\ge 4$.
Let $r=\CL{(n+1)/4}$. When $\theta(K_{n,n})=r$, we will decompose $K_{n,n}$
into $r$ bar visibility graphs. This will leave the case where
$n\equiv 3\mod4$, in which case $r<\theta(K_{n,n})$ and $K_{n,n}$ cannot
decompose into $r$ bar visibility graphs.
Let $U$ and $V$ be the parts of $K_{n,n}$, with $U=\{u_1,\ldots, u_{n}\}$ and
$V=\{v_1,\ldots, v_{n}\}$. Let $p=\FL{n/4}$.
For $n\equiv 0\mod4$, Chen and Yin \cite{CYi16} provided a decomposition of
$K_{n,n}$ into $p+1$ planar subgraphs $\{G_1,\ldots,G_{p+1}\}$. Let
$[p]=\{1,\dots,p\}$. For $1\le j\le p$, let
$U_1^j=\UM i{[p]-\{j\}}\{u_{4i-3},u_{4i-2}\}$, let
$U_2^j=\UM i{[p]-\{j\}}\{u_{4i-1},u_{4i}\}$, let
$V_1^j=\UM i{[p]-\{j\}}\{u_{4i-3},u_{4i-1}\}$, and let
$V_1^j=\UM i{[p]-\{j\}}\{u_{4i-2},u_{4i}\}$.
Figure 1 shows the subgraph $G_j$, for $1\le j\le p$.
Being a $2$-connected planar graph, it is a bar visibility graph.
The subgraph induced by the eight special vertices $\VEC u{4j-3}{4j}$ and
$\VEC v{4j-3}{4j}$ is $K_{4,4}$ minus the edges of the form $u_iv_i$. The
remaining graph $G_{p+1}$ is the matching consisting of $u_iv_i$ for
$1\le i\le 4p$. Again this is a bar visibility graph.
% $K_{4p,4p}$, in which we denote the vertex sets
%$\bigcup\limits^p_{i=1,i\neq r}\{u_{4i-3},u_{4i-2}\}$, $\bigcup\limits^p_{i=1,i\neq r}\{u_{4i-1},u_{4i}\}$,
%$\bigcup\limits^p_{i=1,i\neq r}\{v_{4i-3},v_{4i-1}\}$ and $\bigcup\limits^p_{i=1,i\neq r}\{v_{4i-2},v_{4i}\}$ by $U_1^r$, $U_2^r$, $V_1^r$ and $V_2^r$ respectively.
\begin{figure}[h!]
\begin{center}
\begin{tikzpicture} %%%%%%%%%%%%% 图4第一个图
[inner sep=0pt]
\filldraw [black] (0,2.1) circle (1.4pt)
(2.1,0) circle (1.4pt)
(2.1,4.2) circle (1.4pt)
(4.2,2.1) circle (1.4pt);
\filldraw [black] (1.4,2.1) circle (1.4pt)
(2.8,2.1) circle (1.4pt)
(2.1,1.4) circle (1.4pt)
(2.1,2.8) circle (1.4pt);
\filldraw [black] (0.7,2.5) circle (1.4pt)
(0.7,1.7) circle (1.4pt);
\filldraw [black] (3.5,2.5) circle (1.4pt)
(3.5,1.7) circle (1.4pt);
\filldraw [black] (2.5,0.7) circle (1.4pt)
(1.7,0.7) circle (1.4pt);
\filldraw [black] (2.5,3.5) circle (1.4pt)
(1.7,3.5) circle (1.4pt);
%\filldraw [black] (0.7,2.2) circle (0.7pt)
% (0.7,2.05) circle (0.7pt)
% (0.7,1.9) circle (0.7pt);
%\filldraw [black] (3.5,2.2) circle (0.7pt)
% (3.5,2.05) circle (0.7pt)
% (3.5,1.9) circle (0.7pt);
%\filldraw [black] (2.2,0.7) circle (0.7pt)
% (2.05,0.7) circle (0.7pt)
% (1.9,0.7) circle (0.7pt);
%\filldraw [black] (2.2,3.5) circle (0.7pt)
% (2.05,3.5) circle (0.7pt)
% (1.9,3.5) circle (0.7pt);
\draw (0,2.1)--(2.1,0);\draw (2.1,0)--(4.2,2.1);\draw (2.1,4.2)--(0,2.1);
\draw (4.2,2.1)--(2.1,4.2);
\draw (1.4,2.1)--(2.1,1.4);\draw (2.1,1.4)--(2.8,2.1);\draw (2.8,2.1)--(2.1,2.8);\draw (1.4,2.1)--(2.1,2.8);
\draw (0,2.1)--(0.7,2.5);\draw (0,2.1)--(0.7,1.7);
\draw (1.4,2.1)--(0.7,2.5);\draw (1.4,2.1)--(0.7,1.7);
\draw (2.8,2.1)--(3.5,2.5);\draw (2.8,2.1)--(3.5,1.7) ;
\draw (4.2,2.1)--(3.5,2.5);\draw (4.2,2.1)--(3.5,1.7) ;
\draw (2.1,0)--(2.5,0.7);\draw (2.1,0)--(1.7,0.7);
\draw (2.1,1.4)--(2.5,0.7);\draw (2.1,1.4)--(1.7,0.7);
\draw (2.1,2.8)--(2.5,3.5);\draw (2.1,2.8)--(1.7,3.5);
\draw (2.1,4.2)--(2.5,3.5);\draw (2.1,4.2)--(1.7,3.5);
\draw (2.1,-0.3) node {$v_{4j}$}
(1.9,4.4) node {$v_{4j-3}$}
(-0.4,2.3) node {$u_{4j-1}$}
(4.6,2.25) node {$u_{4j-2}$};
\draw (2.65,1.35) node {$v_{4j-2}$}
(1.55,2.83) node {$v_{4j-1}$}
(1.4,1.75) node {$u_{4j}$}
(2.25,2.1) node {$u_{4j-3}$};
\draw[-](2.1,4.2)..controls+(-1.6,-1.5)and+(-0.2,0.5)..(1.4,2.1);
\draw[-](0,2.1)..controls+(1.5,-1.6)and+(-0.5,-0.2)..(2.1,1.4);
\draw[-](2.1,0)..controls+(1.6,1.5)and+(0.2,-0.5)..(2.8,2.1);
\draw[-](4.2,2.1)..controls+(-1.5,1.6)and+(0.5,0.2)..(2.1,2.8);
%\draw[-](0.7,2) to (-0.5,1.4);\draw (-1.2,1.2) node {\tiny $\bigcup\limits^p_{i=1,i\neq r}\{v_{4i-3},v_{4i-1}\}\triangleq V_1^r$};
\draw (.7,2.1) node {$V_1^j$};
%\draw[-](3.6,2.1) to (4.2,3.2);\draw (4.8,3.5) node {\tiny $\bigcup\limits^p_{i=1,i\neq r}\{v_{4i-2},v_{4i}\}\triangleq V_2^r$};
\draw (3.5,2.1) node {$V_2^j$};
%\draw[-](2.00,0.8) to (3.5,1);\draw (5.00,1.0) node {\tiny $\bigcup\limits^p_{i=1,i\neq r}\{u_{4i-1},u_{4i}\}\triangleq U_2^r$};
\draw (2.1,0.7) node {$U_2^j$};
%\draw[-](2.05,3.5) to (0.7,3.9);\draw (-0.2,4.03) node {\tiny $\bigcup\limits^p_{i=1,i\neq r}\{u_{4i-3},u_{4i-2}\}\triangleq U_1^r$};
\draw (2.1,3.5) node {$U_1^j$};
\end{tikzpicture}
%\\ (a) The graph $G_r\ \ (1\leq r\leq p)$
%\end{center}
%\end{figure}
%\begin{figure}[htp]
%\begin{center}
%\begin{tikzpicture}
%[xscale=1]
%\tikzstyle{every node}=[font=\tiny,scale=1]
%[inner sep=0pt]\tiny
%
%\filldraw [black] (0,1) circle (1.4pt)
% (0,-0.5) circle (1.4pt)
% (1,1) circle (1.4pt)
% (1,-0.5) circle (1.4pt)
% (3,1) circle (1.4pt)
% (3,-0.5) circle (1.4pt)
% (4,1) circle (1.4pt)
% (4,-0.5) circle (1.4pt);
%\draw(4,1)-- (4,-0.5);\draw(3,1)-- (3,-0.5);
%\draw(1,1)-- (1,-0.5);\draw(0,1)-- (0,-0.5);
%\filldraw [black] (1.8,0.3) circle (0.8pt)
% (2,0.3) circle (0.8pt)
% (2.2,0.3) circle (0.8pt);
%\draw (-0.2,0.9) node {\tiny $u_{1}$}
% (-0.2,-0.4) node {\tiny $v_{1}$}
% (0.8,0.9) node {\tiny $u_{2}$}
% (0.8,-0.4) node {\tiny $v_{2}$};
%\draw (3. 5,0.9) node {\tiny $u_{4p-1}$}
% (3.45,-0.4) node {\tiny $v_{4p-1}$}
% (4.35,0.9) node {\tiny $u_{4p}$}
% (4.3,-0.4) node {\tiny $v_{4p}$};
%\end{tikzpicture}
%\\ (b) The graph $G_{p+1}$
\caption{The graph $G_j$ in a planar decomposition of $K_{4p,4p}$.}
\label{figure 1}
\end{center}
\end{figure}
For $n=4p+1$, we add two vertices $u_{4p+1}$ and $v_{4p+1}$,
with $u_{4p+1}$ adjacent to $V$ and $v_{4p+1}$ adjacent to $U$.
The edges incident to $u_{4p+1}$ and $v_{4p+1}$ can be added to the
graph $G_{p+1}$ of the previous case, as shown in Figure 2.
Again this graph is planar and $2$-connected, so again we have a
decomposition $\VEC{\tilde G}1{p+1}$ into $p+1$ bar visibility graphs.
\begin{figure}[htp]
\begin{center}
\vskip-0.8cm\begin{tikzpicture}
[xscale=1]
%\tikzstyle{every node}=[font=\tiny,scale=1]
[inner sep=0pt]
\filldraw [black] (0,1) circle (1.4pt)
(0,-0.5) circle (1.4pt)
(1,1) circle (1.4pt)
(1,-0.5) circle (1.4pt)
(3,1) circle (1.4pt)
(3,-0.5) circle (1.4pt)
(4,1) circle (1.4pt)
(4,-0.5) circle (1.4pt);
\draw(4,1)-- (4,-0.5);\draw(3,1)-- (3,-0.5);
\draw(1,1)-- (1,-0.5);\draw(0,1)-- (0,-0.5);
\filldraw [black] (1.8,0.3) circle (0.8pt)
(2,0.3) circle (0.8pt)
(2.2,0.3) circle (0.8pt);
\draw (-0.3,0.9) node {$u_{1}$}
(-0.3,-0.4) node {$v_{1}$}
(0.7,0.9) node {$u_{2}$}
(0.7,-0.4) node {$v_{2}$};
\draw (2.4,0.9) node {$u_{4p-1}$}
(2.4,-0.4) node {$v_{4p-1}$}
(4.4,0.9) node {$u_{4p}$}
(4.35,-0.4) node {$v_{4p}$};
\filldraw [black] (2,2) circle (1.4pt)
(2,-1.5) circle (1.4pt);
\draw(2,2)-- (0,1);\draw(2,2)-- (1,1);\draw(2,2)-- (3,1);\draw(2,2)-- (4,1);
\draw(2,-1.5)-- (0,-0.5);\draw(2,-1.5)-- (1,-0.5);\draw(2,-1.5)-- (3,-0.5);\draw(2,-1.5)-- (4,-0.5);
\draw (2.5,2.1) node {$v_{4p+1}$}
(2.5,-1.7) node {$u_{4p+1}$};
\draw[-](2,2)..controls+(-3.8,1)and+(-3.8,-1)..(2,-1.5);
\end{tikzpicture}
\vskip-0.8cm\caption{The subgraph $\widetilde{G}_{p+1}$ in the planar
decomposition of $K_{4p+1,4p+1}$}
\label{figure 2}
\end{center}
\end{figure}
For $n=4p+2$, we modify the decomposition given for $K_{4p,4p}$ to accommodate
the edges incident to $\{u_{4p+1},u_{4p+2},v_{4p+1},v_{4p+2}\}$.
First form $\widehat G_{p+1}$ by adding to the matching $G_{p+1}$ the edges
joining $u_{4p+1}$ to $\UM i{[p]}\{v_{4i-2},v_{4i}\}$,
joining $u_{4p+2}$ to $\UM i{[p]}\{v_{4i-3},v_{4i-1}\}$,
joining $v_{4p+1}$ to $\UM i{[p]}\{v_{4i-2},v_{4i-3}\}$, and
joining $v_{4p+2}$ to $\UM i{[p]}\{v_{4i},v_{4i-1}\}$, as shown in Figure 3.
To include the remaining edges involving the four added vertices,
for $1\le j\le p$ obtain $\widehat G_j$ from $G_{j}$ by adding $u_{4p+i}$ to
$U_i^j$ and $v_{4p+i}$ to $V_i^j$, for $i\in\{1,2\}$. Each of these four
vertices gains the two neighbors in $G_j$ that are shared by the vertices of
the set to which it was added. Over the resulting $\VEC{\widehat G}1p$, it
gains precisely the neighbors in the other part that it does not have in
$\widehat G_{p+1}$. We again have $r$ $2$-connected planar graphs decomposing
$K_{n,n}$.
\begin{figure}[htp]
\begin{center}
\begin{tikzpicture}
[xscale=1]
%\tikzstyle{every node}=[font=\tiny,scale=1]
[inner sep=0pt]
\filldraw [black] (0,1) circle (1.4pt)
(0,-0.5) circle (1.4pt)
(1,1) circle (1.4pt)
(1,-0.5) circle (1.4pt)
(1.5,1) circle (1.4pt)
(1.5,-0.5) circle (1.4pt)
(2.5,1) circle (1.4pt)
(2.5,-0.5) circle (1.4pt)
(3,1) circle (1.4pt)
(3,-0.5) circle (1.4pt)
(4,1) circle (1.4pt)
(4,-0.5) circle (1.4pt)
(5.5,1) circle (1.4pt)
(5.5,-0.5) circle (1.4pt)
(6.5,1) circle (1.4pt)
(6.5,-0.5) circle (1.4pt)
(7,1) circle (1.4pt)
(7,-0.5) circle (1.4pt)
(8,1) circle (1.4pt)
(8,-0.5) circle (1.4pt)
(8.5,1) circle (1.4pt)
(8.5,-0.5) circle (1.4pt)
(9.5,1) circle (1.4pt)
(9.5,-0.5) circle (1.4pt);
\draw(4,1)-- (4,-0.5);\draw(3,1)-- (3,-0.5);\draw(1.5,1)-- (1.5,-0.5);\draw(2.5,1)-- (2.5,-0.5);\draw(5.5,1)-- (5.5,-0.5);
\draw(7,1)-- (7,-0.5);\draw(8,1)-- (8,-0.5);
\draw(1,1)-- (1,-0.5);\draw(0,1)-- (0,-0.5);\draw(6.5,1)-- (6.5,-0.5);\draw(8.5,1)-- (8.5,-0.5);\draw(9.5,1)-- (9.5,-0.5);
\filldraw [black] (0.3,0.3) circle (0.8pt) (0.5,0.3) circle (0.8pt) (0.7,0.3) circle (0.8pt);
\filldraw [black] (3.3,0.3) circle (0.8pt) (3.5,0.3) circle (0.8pt) (3.7,0.3) circle (0.8pt);
\filldraw [black] (5.8,0.3) circle (0.8pt) (6,0.3) circle (0.8pt) (6.2,0.3) circle (0.8pt);
\filldraw [black] (8.8,0.3) circle (0.8pt) (9,0.3) circle (0.8pt) (9.2,0.3) circle (0.8pt);
\filldraw [black] (2,2.5) circle (1.4pt)
(7.5,2.5) circle (1.4pt)
(4.8,-2) circle (1.4pt)
(4.8,-3.5) circle (1.4pt);
\draw (-0.55,0.8) node {$v_{4p-2}$}
(-0.55,-0.3) node {$u_{4p-2}$}
(0.75,0.8) node {$v_{6}$}
(0.75,-0.3) node {$u_{6}$}
(1.25,0.8) node {$v_{2}$}
(1.25,-0.3) node {$u_{2}$}
(2.25,0.8) node {$v_{4}$}
(2.25,-0.3) node {$u_{4}$}
(2.75,0.8) node {$v_{8}$}
(2.75,-0.3) node {$u_{8}$}
(3.7,0.8) node {$v_{4p}$}
(3.7,-0.3) node {$u_{4p}$}
(6.0,0.8) node {$v_{4p-1}$}
(6.0,-0.3) node {$u_{4p-1}$}
(6.75,0.8) node {$v_{7}$}
(6.75,-0.3) node {$u_{7}$}
(7.25,0.8) node {$v_{3}$}
(7.25,-0.3) node {$u_{3}$}
(8.25,0.8) node {$v_{1}$}
(8.25,-0.3) node {$u_{1}$}
(8.75,0.8) node {$v_{5}$}
(8.75,-0.3) node {$u_{5}$}
(10.05,0.8) node {$v_{4p-3}$}
(10.05,-0.3) node {$u_{4p-3}$};
\draw (2,2.8) node {$u_{4p+1}$}
(7.5,2.8) node {$u_{4p+2}$}
(4.8,-2.2) node {$v_{4p+2}$}
(4.8,-3.7) node {$v_{4p+1}$};
\draw(2,2.5)-- (0,1);\draw(2,2.5)-- (1,1);\draw(2,2.5)-- (1.5,1);\draw(2,2.5)-- (2.5,1);\draw(2,2.5)-- (3,1);\draw(2,2.5)-- (4,1);
\draw(7.5,2.5)-- (5.5,1);\draw(7.5,2.5)-- (6.5,1);\draw(7.5,2.5)-- (7,1);\draw(7.5,2.5)-- (8,1);\draw(7.5,2.5)-- (8.5,1);\draw(7.5,2.5)-- (9.5,1);
\draw(4.8,-2)-- (2.5,-0.5);\draw(4.8,-2)-- (3,-0.5);\draw(4.8,-2)-- (4,-0.5);\draw(4.8,-2)-- (5.5,-0.5);\draw(4.8,-2)-- (6.5,-0.5);\draw(4.8,-2)-- (7,-0.5);
\draw(4.8,-3.5)-- (0,-0.5);\draw(4.8,-3.5)-- (1,-0.5);\draw(4.8,-3.5)-- (1.5,-0.5);\draw(4.8,-3.5)-- (8,-0.5);\draw(4.8,-3.5)-- (8.5,-0.5);\draw(4.8,-3.5)-- (9.5,-0.5);
\draw[-](2,2.5)..controls+(-5.3,-2.2)..(4.8,-3.5);
\draw[-](7.5,2.5)..controls+(-2.7,-1)..(4.8,-2);
\draw[-](2,2.5)..controls+(2.7,-1)..(4.8,-2);
\draw[-](7.5,2.5)..controls+(5.3,-2.2)..(4.8,-3.5);
\end{tikzpicture}
\caption{The subgraph $\widehat{G}_{p+1}$ in the planar decomposition of $K_{4p+2,4p+2}$}
\label{figure 3}
\end{center}
\end{figure}
%Notice that removing the vertices $u_{4p+2}$ and $v_{4p+2}$ for each graph in \\$\{\widehat{G}_1,\ldots,\widehat{G}_{p+1}\}$ gives a planar decomposition of $K_{4p+1,4p+1}$, but it is a little bit more complicated than the one explicitly constructed for $n=4p+1$ above.
%It is easy to check that, when $n=4p, 4p+1, 4p+2 (p\geq 1)$, all the $p+1$ subgraphs for the planar subgraphs decomposition of $K_{n,n}$, admit visibility representations from Lemma \ref{4}. So their bar visibility number is $p+1$.
The remaining case is $n=4p+3$. A graph $G$ is \textit{thickness $t$-minimal}
if $\theta(G)=t$ and every proper subgraph of $G$ has thickness less than $t$.
When $n=4p+3$, the graph $K_{4p+3,4p+3}$ is a thickness $(p+2)$-minimal graph.
Hobbs and Grossman \cite{HG68} and Bouwer and Broere \cite{BB68} independently
gave two different decompositions of $K_{4p+3,4p+3}$ into planar subgraphs
$\VEC H1{p+2}$. In each case, each $H_{i}$ for $1\le i\le p+1$ is a
2-connected maximal planar bipartite graph (hence a bar visibility graph), and
the graph $H_{p+2}$ contains only one edge. Let this edge be $u_{i}v_{j}$ (it
is $u_{1}v_{1}$ in \cite{HG68} and $u_{4p+3}v_{4p-1}$ in \cite{BB68}).
The bar visibility representation algorithm of \cite{Tamassia86} uses
``$s,t$-numberings'', allowing one to choose any vertex of a bar visibility
graph to be the unique lowest or highest bar in the representation. Since we
have reduced to the case $n\ge4$, we have $p+1\ge2$. Choose a representation
of $H_1$ in which $u_i$ is the lowest bar and a representation of $H_2$ in
which $v_j$ is the highest bar. Place the representation of $H_1$ above the
representation of $H_2$ to incorporate the edge $u_iv_j$ without using an extra
bar for $u_i$ or $v_j$.
We must also show that the bars for $u_i$ in $H_1$ and $v_j$ in $H_2$ can
prevent unwanted visibilities between bars for vertices above and below them.
Since the graph is bipartite, we may assume that bars for the two parts occur
on horizontal lines with those for $U$ having odd vertical coordinates and
those for $V$ having even coordinates. In addition, the bars on one horizontal
line can extend to meet at endpoints to block visibility between higher and
lower bars for the other part (using both the requirement of positive width for
visibility and the fact that we are representing the complete bipartite graph).
The bars can extend so that on each horizontal line the leftmost occupied point
is the same and the rightmost occupied point is the same. Now the two
representations can combine as described above.
\end{proof}
\section{General approach to $b(K_{m,n})$}\label{general}
Henceforth let $f(m,n)=\CL{\FR{mn+4}{2m+2n}}$.
Our proof of $b(K_{m,n})\le f(m,n)$ for $m,n\in\NN$ is independent of the
shorter proof for $m=n$ given in the previous section, which relied on
thickness results from earlier papers. This proof is self-contained.
As mentioned in the introduction, it suffices to produce a $2$-connected
$r$-split of $K_{m,n}$, where $r=f(m,n)$; this is our aim. We will consider
various cases depending on parity. In this section we present the common
aspects of the constructions. We may assume $m\ge n$. Let the two parts of
$K_{m,n}$ be $X$ and $Y$ with $X=\{\VEC x1m\}$ and $Y=\{\VEC y1n\}$.
When $n$ is even and $m> \frac{1}{2}(n^2-2n-4)$, or when $n$ is odd and
$m>n^2-n-4$, we compute $r=\CL{\FR n2}$. In this case let $G_i$ be the subgraph
induced by $X\cup\{y_{2i-1},y_{2i}\}$, except that $G_{(n+1)/2}$ is the
subgraph induced by $X\cup\{y_n\}$ when $n$ is odd. Since $K_{m,2}$ and
$K_{m,1}$ are bar visibility graphs, this decomposes $K_{m,n}$ into
$r$ bar visibility graphs. Note that $3>3^2-3-4$, so when $n=3$ we have
already considered all cases, and henceforth we may assume $n\ge4$.
We have also considered all cases with $r=\CL{\FR n2}$, so
henceforth we may assume $r\leq \FL{\FR{n-1}2}$. Let $s = \CL{\FR n2}-r$.
For fixed $n$, the value of $\FR{mn+4}{2m+2n}$ increases with $m$.
Since $m\ge n$, we have $r\ge\CL{\FR{n^2+1}{4n}}\ge\CL{\FR{n+1}4}$.
Thus $s\le r$. The case $s=r$ requires $s=r=\FR{n+1}4$ and hence
$n\equiv3\mod4$. For $m\in\{n,n+1,n+2\}$, the values of $\FR{mn+4}{2m+2n}$
are $\FR{n+1}4$, $\FR{n+.5+15/(4n+2)}4$, and $\FR{n+1+3/(n+1)}4$,
respectively. The last exceeds $\FR{n+1}4$. Thus the case $s=r$ occurs
if and only if $n\equiv 3\mod4$ and $m\in\{n,n+1\}$. Otherwise, $sj/4$ and there are more than $1+2js/4$ labels
available in each line, which repairs the difficulty when $s$ is odd.
We must also ensure that the labels hit are distinct. The pairs
in $B^+\cup B^-$ seen by $A^+$ range from $\{y_{n/2-2s(q-t)},y_{n-2s(q-t)}\}$
to $\{y_{n/2},y_n\}$, regardless of whether $r$ is even or odd, and the
pairs seen by $A^-$ range from $\{y_1,y_{n/2+1}\}$ to
$\{y_{1+2s(q-t)},y_{n/2+1+2s(q-t)}\}$, as indicated below
$$
\begin{matrix}
y_{1} &\cdots &y_{1+2s(q-t)}&&\vert& &y_{n/2-2s(q-t)} &\cdots &y_{n/2}\\
y_{n/2+1}&\cdots&y_{n/2+1+2s(q-t)}&&\vert& &y_{n-2s(q-t)} &\cdots &y_{n}
\end{matrix}
$$
These labels are distinct if $2+2s(q-t)\le n/2-2s(q-t)$, which reduces to
$2s(q-t)\le n/2-2$. Since $q-t<1$ and $2s(q-t)$ is an integer, it suffices to
have $2s \le n/2-1$. Since $s3/4$, then an extra vertex we get will
be enough. I don't seem to have the page you wrote out for Case 3 with the
shorter brick. Does this simpler construction work?***
\end{proof}
\bigskip
\bigskip
COMMENT!!! If Case 3 works as I have it, then perhaps we can also do Case 2 in
this way and then put all of Cases 1,2,3 into a single construction, with each
of the $j$ extra vertices getting one vertex in $A^+$ and one vertex in $A^-$.
Meanwhile, the aim will be to do the case of odd $n$ in essentially the same
way, with the primary difference being the change in the bricks and in the
cyclic difference between labels on 4-faces. The difference between the
lengths of $B^+$ and $B^-$ should not cause much trouble.
\bigskip
\bigskip
EVERYTHING AFTER THIS IS OLD AND PROBABLY IRRELEVANT!
Step 1. When $m$ is even, this step does nothing. When $m$ is odd, we put
$s$ copies of $x_m$ into $A^+$ (see Figure~\ref{oe}, where $m=13$).
The first copy of $x_m$ is at the first point of $A^+$ and sees copies of
all of $y_1,y_2, y_{n/2+1}, y_{n/2+2}$. The indices on corresponding points
from $B^+$ and $B^-$ always differ by $n/2$. Hence we can proceed making
the $i$th copy of $x_m$ adjacent to the $i$th copies of each of
$y_{2i-1}, y_{2i}$, $y_{n/2+2i-1}, y_{n/2+2i}$ in $B^+\cup B^-$.
Since $s