Abstract of Paper

Hardness Results and Efficient Approximations for Radiocoloring in Planar Graphs
by D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis

Abstract:

The communication in wireless systems, such as radio networks or ad-hoc
mobile networks, is accomplished through exploitation of a rather limited
range of the frequency spectrum. One of the mechanisms utilized in this
direction is to reuse frequencies where this does not result to unacceptable
levels of signal interference. In graph theoretic terms, such issues are
usually modeled by the interference graph $G(V, E)$, where the vertex set
$V$ corresponds to the set of transmitters, and variations of coloring of
the vertices of $G$ have been proposed in order to represent distance
interference constraints. In this paper we study the {\em radiocoloring
problem for planar graphs $G$}. A proper radiocoloring of the planar graph
$G$ with $\lambda$ colors is a function $\Phi: V \rightarrow
\rm{I}\!\!\!\rm{N} $ such that $|\Phi_{u}-\Phi_{v}| \geq 2$, when $u, v$ are
neighbors in $G$ and $|\Phi_{u}-\Phi_{v}|\geq 1$ when the minimum distance
of $u, v$ in $G$ is 2. Also, only $\lambda$ integers are used. The least
possible $\lambda$ is called the radiochromatic number of $G$, denoted as
$X_{r}(G)$.

Notice that $X_{r}(G)$ is also the vertex chromatic number of the {\em
square graph} of $G$, $G^2$, which has the same vertex set
$V$ as $G$ and an edge set $E': \{  u, v \} \in E' $ iff their
{\em minimum} distance is at most $2$ in $G$. Let $\Delta$ be the
maximum degree of the vertices of $G$.
 
In this paper we are interested in the problem of {\em minimizing $\lambda$
(the radiocoloring problem, RAP}):
\begin{enumerate}
\item  We show that {\em RAP is NP-complete for planar graphs}.

\item  We provide an $O(n\Delta)$ time algorithm ($|V|=n$) which obtains a
radiocoloring of a planar graph $G$ that {\em approximates
$X_{r}$ within a ratio which tends to 2} as the maximum
vertex degree $\Delta$ of $G$ increases.

\item  We provide a {\em fully polynomial randomized approximation
scheme} (fpras) for the  {\em number of radiocolorings of a planar
graph}  $G$ with $\lambda$ colors, in the case $\lambda \geq 4
\Delta+50$.
\end{enumerate}