Threshold-Coloring and Unit-Cube Contact Representation of Planar Graphs

In this paper we study threshold-coloring of graphs, where the vertex colors repre-sented by integers are used to describe any spanning subgraph of the given graph as follows. A pair of vertices with a small difference in their colors implies that the edge between them is present, while a pair of vertices with a big color difference implies that the edge is absent. Not all planar graphs are threshold-colorable, but several sub-classes, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact repre-sentation of several subclasses of planar graphs. Variants of the threshold-coloring problem are related to well-known graph coloring and other graph-theoretic problems. Using these relations we show the NP-completeness for two of these variants, and de-scribe a polynomial-time algorithm for another