On radiocoloring hierarchically specified planar graphs: PSPACE-completeness and approximations

Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification model, considered in this work, is that of Lengauer [21,22], referred to as L-specifications. In this paper we discuss a restriction on the L-specifications resulting to graphs which we call Well-Separated (WS). This class is recognized in polynomial time. In this work we study the Radiocoloring Problem (RCP) on WS L-specified hierarchical planar graphs. The optimization version of RCP studied here, consists in assigning colors to the vertices of a graph, such that any two vertices of distance at most two get different colors. The objective here is to minimize the number of colors used. We first show that RCP is PSPACE-complete for WS L-specified hierarchical planar graphs. Second, we present a polynomial time 3-approximation algorithm as well as a more efficient asymptotic 10/3- approximation algorithm for RCP on graphs of this class. We note that, the best currently known approximation ratio for the RCP on ordinary (non-hierarchical) planar graphs of general degree is 5/3 asymptotically ([27,28]).