2-coloring of 3-uniform hypergraphs. The polynomial-time reduction from a given graph to is as follows. Let $H = (X,F)$ be an instance of a 3-uniform hypergraph. $H$ is said to be 2-colorable if there is an assignment of two colors with no monochromatic edge. In the following part, when we write “uniformly distributed,” we mean the Euclidean distance between two sensor nodes is less than one unit. We construct the gadget to perform the reduction as follows.

1.  We have $|X|$ vertical, and $2|F|+2$ horizontal straight lines. Each of them are parallel to either $x$-axis or $y$-axis.

2.  All the vertical lines are colored black, and spaced equally. These lines are called *vertex lines*, that represent the vertex set of $H$. The Euclidean distance between each pair of vertical line is greater than two units, and less than three units.

3.  One of the horizontal lines, called the *main line*, is given by the equation $y = 0$. This line is colored black. There are sufficient number of uniformly distributed wireless sensor nodes on the main line, including the intersection points of the main line and the vertex lines.

4.  In order to fix the configuration, there exists a *support 