1 Introduction

Recently, Bishnu et al. [6] initiated the study of grid-obstacle representations. Here the vertices of a graph \(G=(V,E)\) are mapped to points in an integer grid, and other grid-points are marked as obstacles in such a way that (v, w) is an edge of G if and only if there exists an xy-monotone path in the grid from v to w that contains no obstacle-point and no point that belongs to some vertex \(\ne v,w\). See also Fig. 1b. This is a special case of a more general problem, which asks for placing points and obstacles in the plane such that an edge (v, w) exists if and only if there is a shortest path (in some distance metric) from v to w that does not intersect obstacles. See also Alpert et al. [2], who initiated the study of obstacle numbers, and [9] and the references therein for more recent developments.

Bishnu et al. [6] showed that any planar graph has a grid-obstacle representation in 2D, and every graph has a grid-obstacle representation in 3D. The main idea was to use a straight-line drawing, and then approximate it by putting a sufficiently fine grid around it that consists of obstacles everywhere except near the edge. The analysis of how fine a grid is required is not straightforward; Bishnu et al. claimed that in 2D an \(O(n^2)\times O(n^2)\)-grid is sufficient. They did not give bounds for the size needed in 3D (but it clearly is polynomial and at least \(\varOmega (n^2)\) in each dimension). Pach showed that not all bipartite graphs have grid-obstacle representations in 2D [12].

In this paper, we improve the grid-size bounds of [6]. In particular, rather than converting a straight-line drawing directly into a grid-obstacle representation, we first convert it into a visibility representation or an orthogonal drawing that has special properties, but resides in a linear-size grid. This can then be easily converted to a grid-obstacle representation. Thus we obtain 2D grid-obstacle representations for planar graphs in an \(O(n)\times O(n)\)-grid, and 3D grid-obstacle representations for all graphs in an \(O(n)\times O(n)\times O(n)\)-grid.

We then discuss the case with the restriction that vertices act as obstacles for edges not incident to them, and show that sometimes this restriction can be dropped. We hence obtain non-blocking grid-representations in 2D for all planar bipartite graphs and in 3D for arbitrary bipartite graphs.

The latter has applications: we can use the constructions for hardness proofs for a polygon-guarding problem. A point guard g is said to staircase guard (or s-guard for short) a point p inside an orthogonal polygon P if p can be reached from g by a staircase; that is, an orthogonal path inside P that is both x- and y-monotone. In the s-guarding problem, the objective is to guard an orthogonal polygon with the minimum number of s-guards. Motwani et al. [11] proved that s-guarding is polynomial on simple orthogonal polygons. Gewali and Ntafos [10] proved that the problem is NP-hard in 3D; since they reduce from vertex cover in graphs with maximum degree 3 this in fact implies APX-hardness in 3D [1]. To our knowledge, however, the complexity was open for 2D polygons with holes. Using non-blocking grid-representations, we show that it is NP-hard.

2 2D Grid-Obstacle Representations

Let \(G=(V,E)\) be a planar graph. To build a grid-obstacle representation, we use a visibility representation where every vertex is represented by a bar (a horizontal line segment), and every edge is represented by a vertical line segment between the bars corresponding to the endpoints of the edge [13,14,15]. We need here a construction with a special property, which can easily be achieved by “shifting” where the edges attach at the vertices (see the full paper for a direct proof). See also Fig. 1a.

Lemma 1

Every planar graph has a visibility representation in an \(O(n)\times O(n)\)-grid for which any vertex-bar can be split into a left and right part such that all downward edges attach on the left and all upward edges attach on the right.

Fig. 1.
figure 1

A special visibility representation gives a grid-obstacle representation.

Full size image

Now convert such a visibility representation into a grid-obstacle representation. First, double the grid so that no two grid-points on edge-segments or vertex-bars are adjacent unless the corresponding graph-elements were. For each vertex v, assign as vertex-point some grid-point that lies between the two parts of the bar of v; this exists since we doubled the grid. The obstacles consist of all grid points that are not on some edge segment or vertex bar. Clearly, the representation is in an \(O(n)\times O(n)\)-grid. In the full paper, we show that this is a grid-obstacle representation, and so we have:

Theorem 1

Every planar graph has a 2D grid-obstacle representation in an \(O(n)\times O(n)\)-grid.

One can easily argue that any straight-line drawing of a planar graph of height H can be converted into a visibility representation of height 2H and width O(n) (see also [4]). Then we can apply the same approach as above. Based on drawings for trees [8], outer-planar graphs [3] and series-parallel graphs [3], we hence get:

Corollary 1

Every tree and every outer-planar graph has a 2D grid-obstacle representation in an \(O(\log n)\times O(n)\)-grid. Every series-parallel graph has a 2D grid-obstacle representation in an \(O(\sqrt{n})\times O(n)\)-grid.

3 3D Grid-Obstacle Representation

In this section, we argue that a similar (and even simpler) construction gives a grid-obstacle representation in 3D. We obtain this by building an orthogonal representation first that has special properties. This representation is not quite a graph drawing, because edges may overlap; this will not create problems for the obstacle representation later.

Enumerate the vertices as \(v_1,\dots ,v_n\) in arbitrary order. Place \(v_i\) at (i, i, i). To draw an edge \((v_i,v_j)\) with \(i<j\), we use the path \((i,i,i)-(j,i,i)-(j,i,j)-(j,j,j)\) along the cube spanned between the two points. See Fig. 2. Observe that all edges \((v_h,v_i)\) with \(h<i\) reach \(v_i\) from the \(y^-\)-side and that all edges \((v_i,v_j)\) with \(i<j\) leave \(v_i\) at the \(x^+\)-side. Edges incident to \(v_i\) may overlap along these two sides, but otherwise there are no overlaps or crossings in the drawing. Also, we clearly reside in an \(n\times n\times n\)-grid.

Fig. 2.
figure 2

A 3D orthogonal representation of \(K_4\), and converting it into a grid-obstacle representation. All grid-points that are not shown are blocked by obstacles.

Full size image

Now double the grid, then cover any grid-point by an obstacle unless it is used by a vertex or an edge. One can easily argue that the result is a grid-obstacle representation (see the full paper for a formal proof), and we have:

Theorem 2

Every graph has a 3D grid-obstacle representation in an \(O(n)\times O(n)\times O(n)\)-grid.

Notice that the obstacle in this case can be made to be just one polyhedron (albeit of high genus).

4 Non-blocking Grid-Obstacle Representations

In our definition of grid-obstacle representation, we required that the grid point of any vertex v acts as an obstacle to any other path. The main reason for this is that otherwise paths could “seep through” a vertex, creating unwanted adjacencies. In this section, we consider non-blocking grid-obstacle representations, which means that vertices do not act as obstacles.

4.1 Planar Bipartite Graphs

We first give an algorithm for non-blocking grid-obstacle representation of planar bipartite graphs. It is known that any such graph \(G=(A\cup B,E)\) has an HH-drawing [5], i.e., a planar drawing where all vertices in A have positive y-coordinate, all vertices in B have negative y-coordinate, every edge is drawn with at most one bend, and all bends have y-coordinate 0. See also Fig. 3.

In particular, we know that every edge is drawn y-monotonically. Any such drawing can be converted into a visibility representation [4] where the y-coordinate of every vertex is unchanged. So we obtain:

Lemma 2

Let \(G=(A\cup B,E)\) be a planar bipartite graph. Then, there exists a visibility representation of G such that all vertices in A have only neighbours below, and all vertices in B have only neighbours above.

Now create an obstacle representation as before by doubling the grid, and placing obstacles at all grid-points that are not used by the drawing. Place each vertex \(a\in A\) at the rightmost grid-point of the bar of a, and each \(b\in B\) at the leftmost grid-point of the bar of b. One easily verifies that this is a non-blocking grid-obstacle representation: For each vertex a in A, no xy-monotone path can go through the grid-point of a without ending there, because no grid-point higher than a can be reached when going through a. Similarly one argues for B, and so we have:

Theorem 3

Every planar bipartite graph has a non-blocking grid-obstacle representation in an \(O(n)\times O(n)\)-grid.

Fig. 3.
figure 3

An HH-drawing of a planar bipartite graph, and converting it to a non-blocking grid-obstacle representation.

Full size image

4.2 Application to Staircase Guarding

Recall that the s-guarding problem consists of finding the minimum set S of points in a given orthogonal polygon P such that for any \(q\in P\) there exists a \(p\in S\) that is connected to q via a staircase inside P. Using non-blocking grid-obstacle representations, we can show:

Theorem 4

s-guarding is NP-hard on orthogonal polygons with holes.

Fig. 4.
figure 4

The polygon for the graph in Fig. 3, and gadgets that we attach.

Full size image

Proof

We reduce from minimum dominating set, i.e., the problem of finding a set D of vertices in a graph such that every vertex is either in D or has a neighbor in D. This is NP-hard, even on planar bipartite graphs [7]. Given a planar bipartite graph \(G=(A\cup B, E)\), construct the non-blocking grid-obstacle representation \(\varGamma \) from Theorem 3. Let \(P'\) consist of all unit squares (pixels) around grid-points that are not in an obstacle. The obstacles of \(\varGamma \) become holes in \(P'\). Now for any vertex \(a\in A\) extend the bar of a slightly rightward beyond the last edge, and for every \(b\in B\) extend the bar leftward beyond the last edge. Finally, at every edge e, attach two “spirals” on the left and right side of its vertical segment; the one on the left curls upward while the on the right curls downward. See Fig. 4. These spirals are small enough that they fit within the holes of \(P'\), without overlapping other parts of \(P'\) or each other. We show in the full paper that G has a dominating set of size k if and only if this polygon can be s-guarded with \(2|E|+k\) guards. This proves the theorem.     \(\square \)

4.3 3D Grid-Obstacle Representation of Bipartite Graphs

In 3D, all bipartite graphs have a non-blocking grid-obstacle representation: Enumerate the vertices as \(A=\{a_1,\dots ,a_\ell \}\) and \(B=\{b_1,\dots ,b_k\}\). Place a point for vertex \(a_i\) at (0, i, 0) and a point for vertex \(b_j\) at (j, 0, 1). Route each edge \((a_i,b_j)\) as the orthogonal path \((0,i,0)-(j,i,0)-(j,i,1)-(j,0,1),\) and observe that two paths overlap in the \(x^+\)-direction at \(a_i\) if they both begin at \(a_i\), or overlap in the \(y^+\)-direction at \(b_j\) if they both end at \(b_j\), but otherwise there is no overlap. Now obtain the grid-obstacle representation as before by doubling the grid and making grid-points obstacles unless they are used by vertices and edge-paths (Fig. 5). As before one argues that this is indeed a non-blocking grid-obstacle representation and so we have:

Theorem 5

Every bipartite graph has a 3D non-blocking grid-obstacle representation.

Fig. 5.
figure 5

A 3D orthogonal representation of \(K_{2,3}\), and converting it into a grid-obstacle representation. Grid-points not shown are covered by obstacles.

Full size image

5 Conclusion

In this paper, we studied grid-obstacle representations. We gave constructions with smaller grid-size for planar graphs in 2D and all graphs in 3D. If the graph is bipartite then we can construct representations where vertices are not considered obstacles. We used these types of representation to prove NP-hardness of the s-guarding problem in 2D polygons with holes.

It remains open whether an asymptotically smaller grid and/or fewer obstacles might be enough. If we allow obstacles to be polygons rather than grid-points, we use (in Theorems 1 and 3) one obstacle per face of the planar graph, or \(\varTheta (n)\) in total. For grid-obstacle representations that use straight-line segments, rather than xy-monotone grid-paths, significantly fewer obstacles suffice [9]. Can we create grid-obstacle representations with o(n) obstacles, at least for some subclasses of planar graphs? Another direction for future work would be to find other classes of graphs for which we can construct non-blocking grid-obstacle representations. Does this exist for all planar graphs in 2D?