{'fraction_non_alphanumeric': 0.06095638465580662, 'fraction_numerical': 0.01183889215171092, 'mean_word_length': 3.5974136705982662, 'pattern_counts': {'":': 0, '<': 80, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 40, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Advancing Through Terrains

We study terrain visibility graphs, a well-known graph class closely related to polygon visibility graphs in computational geometry, for which a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted attention in the context of time series analysis with various practical applications in areas such as physics, geography and medical sciences. We make progress in understanding terrain visibility graphs by providing several graph-theoretic results. For example, we show that they cannot contain antiholes of size larger than five. Moreover, we obtain two algorithmic results. We devise a fast output-sensitive shortest path algorithm on arbitrary induced subgraphs of terrain visibility graphs and a polynomial-time algorithm for \textsc{Dominating Set} on special terrain visibility graphs (called funnel visibility graphs).


Introduction
Visibility graphs are a fundamental concept in computational geometry. For a given set of geometrical objects (e.g. points, segments, rectangles, polygons) they encode which objects are visible to each other. To this end, the objects form the vertices of the graph and there is an edge between two vertices if and only if the two corresponding objects "can see each other" (for a specified notion of visibility). Visibility graphs are well-studied from a graph-theoretical perspective and find applications in many real-world problems occurring in different fields such as physics [14,26,13], robotics [6], object recognition [29], or medicine [4,17].
In this work, we study visibility graphs of 1.5-dimensional terrains (that is, xmonotone polygonal chains). This graph class has been studied since the 90's [3] and found numerous applications in analyzing and classifying time series in recent years [24,14,26,13,30,17]. However, a precise graph-theoretical characterization is an open problem. While a necessary condition for terrain visibility graphs is known, it is open whether this is also sufficient (see Section 2).
In Section 3, we make progress towards a better understanding of terrain visibility graphs by showing that they do not contain antiholes of size larger than five. Moreover, we show that terrain visibility graphs do not include all unit interval graphs (which are hole-free). Furthermore, we give an example showing that terrain visibility graphs are not unigraphs, that is, they are not uniquely determined by their degree sequence up to isomorphism.
Besides these graph-theoretical findings, our main contributions are two algorithmic results: In Section 4, we develop an algorithm computing shortest paths in arbitrary induced subgraphs of terrain visibility graphs (in fact, the algorithm even works for a more general class of graphs satisfying a weaker condition) in O(d * log ∆) time, where d * is the length of the shortest path and ∆ is the maximum degree (also O(d * ) time is possible with an O(n 2 )-time preprocessing). Section 5 presents an O(n 4 )-time algorithm for Dominating Set on a known subclass of terrain visibility graphs called funnel visibility graphs.
Related Work. For a general overview on visibility graphs and related problems see the survey by Ghosh and Goswami [19]. As regards the origin of terrain visibility graphs, Abello et al. [3] studied visibility graphs of staircase polygons which are closely related to terrain visibility graphs as Colley [11] showed that they are in one-to-one correspondence with the core induced subgraphs of staircase polygon visibility graphs. Abello et al. [3] described three necessary properties that are satisfied by every terrain visibility graph and conjectured that these are actually sufficient. Moreover, they showed that one can reconstruct (a possible) slope ordering from the graph with given vertex ordering. Evans and Saeedi [15] gave a simpler proof for the results of Abello et al. [3]. Abello and Egecioglu [2] showed that visibility graphs of staircase polygons with unit step-length can be recognized via linear programming and that not all staircase polygon visibility graphs can be represented with unit steps. Choi et al. [10] studied another subclass of terrain visibility graphs called funnel visibility graphs which is linear-time recognizable (also studied by Colley et al. [12]).
Lacasa et al. [24] introduced terrain visibility graph (under the name of time series visibility graphs) in the context of time series analysis. A variant (called horizontal visibility graphs) where two vertices can only see each other horizontally was later introduced by Luque et al. [27]. Horizontal visibility graphs were fully characterized by Gutin et al. [21] who showed that these are exactly the outerplanar graphs with a Hamiltonian path. Moreover, Luque and Lacasa [28] showed that certain canonical horizontal visibility graphs are uniquely determined by their degree sequence.
Notably, the Terrain Guarding problem, that is, selecting k terrain points that guard the whole terrain (which is closely related to Dominating Set on terrain visibility graphs) has been extensively studied in the literature and is known to be NP-hard [23] even on orthogonal terrains [7]. It has recently been studied from a parameterized perspective [5].

Preliminaries
We assume the reader to be familiar with basic concepts and classes of graphs (refer to Brandstädt et al. [8] for an overview).
A (1.5-dimensional) terrain is an x-monotone polygonal chain in the plane defined by a set V of terrain vertices with pairwise different x-coordinates. For two terrain vertices p, q, we write p < q if p is "left" of q, that is, The corresponding terrain visibility graph is defined on the set of terrain vertices where two vertices p and q are adjacent if and only if they see each other, that is, there is no vertex between them that lies on or above the line segment connecting p and q (see Figure 1 for an example). Formally, there exists an edge {p, q}, for p < q, if and only if all terrain vertices r with p < r < q satisfy Hershberger [22] gave an algorithm to compute the visibility graph of a given terrain with a running time that is linear in the size of the graph.
Let p ∈ V be a terrain vertex and q, r be the vertices immediately to its left and right. We call p convex if q and r see each other. Otherwise it is called reflex. The leftmost and rightmost vertex of a terrain are neither convex nor reflex.
Clearly, every terrain visibility graph contains a Hamiltonian path along the order of the terrain vertices. Moreover, the visibility graph of a terrain is invariant under some affine transformation, in particular scaling or vertical shearing.
The following are two elementary properties of terrain visibility graphs (we stick to the names coined by Evans and Saeedi [15]). Two edges {p, q} and {r, s} are said to be crossing if the corresponding line segments cross, i.e. if p < r < q < s. The first property states that two crossing edges imply the existence of another edge.
X-property: Let p, q, r, s be four terrain vertices with p < q < r < s. If p sees r and q sees s, then p sees s.
The X-property holds because q must lie below the line segment through p, r and r must lie below the line segment through q, s. Thus, the line segment between p and s is always above one of these two line segments, so it cannot be obstructed by any vertex. bar-property: If p, q are two non-consecutive terrain vertices that can see each other, then there is a vertex r between p and q that can see both of them.
The bar-property is immediate if we first apply a vertical shear mapping such that p y = q y . Then, r is simply the vertex between p and q which has maximal y-coordinate.
It is conjectured that these two properties together with the existence of a Hamiltonian path fully characterize terrain visibility graphs.

Graph Properties
In this section we prove our graph-theoretical results.

Induced Subgraphs
It is known that terrain visibility graphs can contain an induced C 4 [16,18]. It is further known that, whenever four vertices p 1 , p 2 , p 3 , p 4 of a terrain visibility graph form an induced C 4 (in that order), then they cannot satisfy p 1 < p 2 < p 3 < p 4 since this violates either the X-property or the bar-property [18,1]. This leads to the following simple observation. Proof. Assume that the leftmost vertex of p 1 , p 2 , p 3 , p 4 has an edge to the second leftmost vertex. If it also has an edge to the rightmost vertex, then this case is equivalent (up to cyclic shifting and order reversal) to the case p 1 < p 2 < p 3 < p 4 , which is not possible [18,1]. Hence, it has an edge to the second rightmost vertex. But then the X-property is violated since there is also an edge from the second leftmost to the rightmost vertex.
Thus, there cannot be an edge between the two leftmost vertices, which means these are either p 1 and p 3 or p 2 and p 4 .
We can generalize this observation to larger induced cycles: While C k may appear as induced subgraph for any k, its vertices can only occur in a specific order. For an example consider Fig. 2. Note that this construction can be generalized to any k ≥ 4 by changing the number of vertices on the bottom middle path.
We start with the following basic lemma (which can also be derived from the Xproperty and bar-property).
Lemma 3.2. Let G be a terrain visibility graph and p, q, r three of its terrain vertices with p < q < r. If p sees q and r, but q does not see r, then there exists b ∈ V (G) with q < b < r that sees both, p and q.
Proof. Since p sees q and r, the three points p, q, r are oriented counterclockwise. Since q does not see r, there must be some vertex that lies above the line segment connecting q, r. Let b be the leftmost such vertex, then b clearly sees q and is located inside the triangle defined by p, q, r. Thus, each point of the line segment connecting p and b lies either above the line segment connecting p and q or above the line segment connecting q and b. In particular, it does not pass below any vertex.
For the vertex ordering of induced cycles, we can now derive the following. Proof. Assume without loss of generality that p 1 > p 3 . Since k ≥ 4, by Lemma 3.2, there is a vertex q between p 3 and p 1 that can see p 2 and p 3 .
By the X-property, p 4 , . . . , p k−1 must all lie between p 2 and p 1 . Suppose that there exists i > 3 (chosen minimally) such that p i > q. Then, by the X-property, p 2 would see p i , which is a contradiction. Since p 3 sees q but not p 1 , p k must even lie to the left of p 3 by the X-property. Now, assume that there exists j > 3 (chosen maximally) such that p j > p 3 . Then, p j would see p 2 by the X-property. Therefore, p 4 , . . . , p k must all be to the left of p 3 . Lemma 3.3 now leads to a specific vertex ordering for an induced cycle. Proposition 3.4. Let G be a terrain visibility graph and let p 1 , . . . , p k ∈ V (G) form an induced cycle (in this order) with k ≥ 4. Then, p 1 > p 3 > p 4 > · · · > p k > p 2 holds up to cyclic renaming and order reversal.
Proof. We assume without loss of generality that p 2 is the leftmost vertex and that p 1 > p 3 . By Lemma 3.3, it follows p 4 , . . . , p k ⊂ [p 2 , p 3 ]. In particular, p 1 is the rightmost vertex. Thus, a mirrored version of Lemma 3.3 applies to the shifted sequence p k , p 1 , p 2 , . . . , p k−1 , Now, assume towards a contradiction that there exists 3 < i < k − 1 with p i < p i+1 , where i is chosen minimally. Let j be minimal such that p j < p i , that is, p j−1 > p i . Note that j > i by the choice of i. Let ℓ < i be maximal with p ℓ > p j−1 , that is, p ℓ+1 < p j−1 . Note also that p ℓ+1 ≥ p i by the choice of i. Then, p ℓ > p j−1 > p ℓ+1 > p j . Hence, by the X-property, G contains the edge {p ℓ , p j }. Since p 3 , p 4 , . . . , p k form an induced path, this implies j = ℓ + 1, contradicting the fact that j > i > ℓ. Interestingly, we can use Observation 3.1 to show that terrain visibility graphs do not contain large antiholes (an induced subgraph isomorphic to the complement of a cycle). Proof. Let p 1 , . . . , p k induce an antihole in G in this order with k ≥ 6. Observe that for any i, j with |i − j| / ∈ {0, 1, 2} (mod k), the vertices p i , p j , p i+1 , p j+1 form an induced 4-cycle in this order.
Assume without loss of generality that p 1 is the rightmost vertex. Then, for each j = 4, . . . , k − 2, we apply Observation 3.1 to the C 4 on p 1 , p j , p 2 , p j+1 which yields that either p j and p j+1 or p 1 and p 2 are the two rightmost. It follows by assumption that p 1 and p 2 are the rightmost. Hence, p 5 , . . . , p k−1 are all to the left of p 2 . Now, for j = 5, . . . , k − 1, we apply Observation 3.1 to p 2 , p j , p 3 , p j+1 and obtain that p 5 , . . . , p k are also to the left of p 3 . Finally, for j = 6, . . . , k we use the same argument on p 3 , p j , p 4 , p j+1 (where p k+1 = p 1 ) and obtain that p 6 , . . . , p k , p 1 are to the left of p 3 . This contradicts our assumption that p 1 is the rightmost vertex.
Considering possible subclasses of terrain visibility graphs, we close this subsection by showing that terrain visibility graphs do not include all unit interval graphs. The unit interval graph depicted in Figure 3 is not a terrain visibility graph. This is because it only has one Hamiltonian path (up to isomorphism) and the ordering given by this path violates the X-property. It is open whether every unit interval graph can appear as an induced subgraph of a terrain visibility graph.

Degree Sequences
Luque and Lacasa [28] studied the degree sequences of horizontal visibility graphs in order to explain why measures based on the degree sequence of horizontal visibility graphs of time series perform well in classification tasks. Their conclusion is that the degree sequence essentially contains all information of the underlying time series. Formally, they show that (canonical) horizontal visibility graphs are uniquely determined by their degree sequence.
In contrast, this not the case for terrain visibility graphs since the two terrain visibility graphs in Figures 4 and 5 both have the ordered degree sequence (7,4,3,4,5,7,4,4,4,6,4) and are not isomorphic (since the unique degree-3 vertex has a degree-7 neighbor in one graph but not in the other).

Shortest Paths
A natural example for the occurrence of terrain visibility graphs is a network of stations communicating via line-of-sight links, e.g. radio signals. A common task is to determine the shortest path between two vertices s < t. If the length of a path is measured via Euclidean distance, then the easy solution is to always go to the right as far as possible without going beyond t. In general, computing Euclidean shortest paths in polygon visibility graphs is a well-studied problem and linear-time algorithms are known [20].
But a more realistic distance measure in the above scenario is the number of edges, as edge travel times might be negligible in comparison to the processing times at the vertices. In this setting, the situation becomes more difficult since it might now be better to move in the opposite direction first. Nevertheless, the "go as far as possible" principle still proves very useful here. To the best of our knowledge, no specific algorithm for unweighted shortest path computation in terrain (or polygon) visibility graphs has been developed so far.
The algorithm we describe in this section does not only work for terrain visibility graphs but in fact for every graph that allows for a vertex ordering fulfilling the Xproperty. Note that this is true for every induced subgraph of a terrain visibility graph. Interestingly, the converse is not true since the complement of C 6 (that is, a size-6 antihole) can satisfy the X-property (see Figure 6) but cannot be an induced subgraph of a terrain visibility graph (Theorem 3.5).
Hence, our algorithm can be used in an even more general context. For example, in the communication scenario above, we can also handle vertices which obstruct communication but are not stations themselves. Hence, in this section, we assume G to have a (known) vertex ordering satisfying the X-property. Furthermore, we assume s and t to be two vertices of G with s < t and dist(s, t) = d * < ∞, where dist(s, t) denotes the length (that is, the number of edges) of a shortest path from s to t.
We start with the crucial observation that a shortest path contains at most one pair of crossing edges. Proof. Let P be a shortest s-t-path and {v, v ′ }, {w, w ′ } two crossing edges with v < w < v ′ < w ′ . By the X-property, G contains the edge {v, w ′ }. Since P is a shortest path and thus also an induced path, it must contain that edge (see Figure 7). We claim that no Hence, by the X-property, P would have to contain the edge {x, w ′ }, which is not possible since w ′ would be incident to three edges of P . Otherwise, if v < x < v ′ < x ′ , then P would contain the edge {v, x ′ }, which is again not possible. By symmetry, no other edge of P can cross {w, w ′ }. Consequently, P contains only vertices in [v, w ′ ] since otherwise P would contain an edge from a vertex u ∈ [v, w ′ ] to a vertex x with v < x < w ′ such that {u, x} crosses {v, v ′ } or {w, w ′ }. It follows that P cannot contain any other pair of crossing edges between vertices in [v, w ′ ] since the same argument would apply to that pair.
We denote a shortest s-t-path P of length d * by its vertices s = p 0 , p 1 , . . . , p d * = t and define li(P ) to be the index of the leftmost vertex of P . Analogously, ri(P ) is the index of the rightmost vertex of P . The following can be obtained from Lemma 4.1 (see also Fig. 9 (iii)). Moreover, if P contains a pair of crossing edges, then ri(P ) = li(P ) − 1 and p i < p j holds for all i < ri(P ) < li(P ) < j.
Proof. If ri(P ) < li(P ), then P must contain a pair of crossing edges between the subpaths from s to p ri(P ) and from p li(P ) to t. Conversely, if P contains a pair of crossing edges, then, by Lemma 4.1, the two crossing edges must be {p ri(P )−1 , p ri(P ) } and {p li(P ) , p li(P )+1 }. This implies that P contains the edge {p ri(P ) , p li(P ) }, which implies ri(P ) = li(P ) − 1. Then, for all i < ri(P ) < li(P ) < j, it holds that p i < p j since P has no other crossing edges and p ri(P )−1 < p li(P )+1 .
Clearly, Lemma 4.2 implies that li(P ) < ri(P ) if and only if P contains no crossing edges. Moreover, the following holds (see Fig. 9 (i) and (ii)). Lemma 4.3. Let P be a shortest s-t-path with li(P ) < ri(P ). Then, p i < p j holds for all i < li(P ) < j and all i < ri(P ) < j.
Proof. We prove both cases simultaneously. Assume towards a contradiction that p j < p i , then we have p li(P ) < p j < p i < p ri(P ) . Consider the subpath P 1 of P that connects p i with p li(P ) and the subpath P 2 of P that connects p j with p ri(P ) . These two subpaths are vertex-disjoint and must thus be crossing, meaning that there is a pair of crossing edges e 1 , e 2 with e 1 ⊆ P 1 and e 2 ⊆ P 2 . By Lemma 4.2, this implies ri(P ) < li(P ), which is a contradiction.
In combination, Lemma 4.2 and Lemma 4.3 imply the following corollary.
Corollary 4.4. For a shortest s-t-path P , it holds that all vertices p i with i < ri(P ) satisfy p i < t and all vertices p i with i > li(P ) satisfy p i > s.
The results derived above characterize the global structure of a shortest s-t-path. Next, we will investigate the local structure. The most important consequence of the X-property is that large steps are usually better than small steps. We formalize this in the following.
Define α s (k) as the leftmost and β s (k) as the rightmost vertex that can be reached from s by a path of length at most k that only uses vertices v ≤ t. We symmetrically define α t (k) as the rightmost and β t (k) as the leftmost vertex reachable from t by a path of length at most k using only vertices v ≥ s.
The following lemma shows that there is a shortest path from s to α s (k) that uses only vertices in {α s Proof. Clearly, the statement trivially holds for k = 1 and if α s (k) = α s (k − 1). Hence, assume that k ≥ 2 and α s (k) = α s (k − 1). In the following, we only consider vertices to the left of t, which is why we assume that t is the rightmost vertex for the remainder of this proof. Let {x, α s (k)} be the last edge of a shortest path from s to α s (k). By definition, we have α s (k − 1) ≤ x.
If x < s, then let Q be a shortest path from s to α s (k − 1). If x is a vertex of Q, then x = α s (k − 1) (otherwise we have a path from s to α s (k) of length at most k − 1 implying α s (k) = α s (k − 1)) and we are done. Otherwise, Q contains an edge {y, y ′ } with y < x < y ′ . By the X-property, there is an edge between α s (k) and y ′ , which yields a path of length at most k − 1 between s and α s (k), implying α s (k − 1) = α s (k).
If x > s, then let Q be a shortest path from s to β s (k − 1). If x is a vertex of Q, then x = β s (k − 1) (otherwise we have a path from s to α s (k) of length at most k − 1 implying α s (k) = α s (k − 1)) and we are done. Otherwise, Q contains an edge {y, y ′ } with y < x < y ′ . By the X-property, there is an edge between α s (k) and y ′ , which yields a path of length at most k − 1 between s and α s (k), implying α s (k − 1) = α s (k).
Due to symmetry, Lemma 4.5 also holds if one exchanges α and β, and also when s is replaced by t. With the following lemma, we will be able to restrict our search for a shortest s-t-path mostly to the α and β vertices. Lemma 4.6. There is a shortest s-t-path P = p 0 , . . . , p d * such that (i) p i ∈ {α s (i), β s (i)} for all i < ri(P ), and Figure 8: Left: The situation described in the proof of Lemma 4.6. Note that the proof shows that µ = i (that is, q µ = β s (i)) and ν = i + 1 (that is, p ν−1 = p i ). The dashed edge from s to q µ−1 indicates a path of length i − 1, whereas the dashed edge from p ν to t indicates a path of length d * − i − 1. Right: The (similar) situation for the case p i < s. Note that also here µ = i and ν = i + 1 holds (that is, p ν−1 = p i and q µ = α s (i)).
Before moving on, we show that if the chosen shortest path P in the above argument satisfies (ii), then also P ′ does so. This observation will be helpful for the second part of the proof. To this end, note that we concluded above that µ ′ = µ = i and ν = i+1, which implies that p i+1 < p i . Assume towards a contradiction that p j < p i+1 for some j < i. Then, there must be a pair of crossing edges from the subpaths from p j to p i and from p i+1 to t. By the X-property, there is now an edge between two non-consecutive vertices of P , contradicting the fact that P is an induced path. Thus, p i+1 must be to the left of p 0 , . . . , p i . This implies i < li(P ), and thus, p li(P ) is also a vertex of P ′ . Furthermore, all of q 0 , . . . , q i must be to the right of p li(P ) because otherwise P ′ would contain a pair of crossing edges from the subpaths from s to q i and from p li(P ) to t. Thus, li(P ) = li(P ′ ). We conclude that i < li(P ) = li(P ′ ), that is, P ′ also satisfies (ii). Now, assume towards a contradiction that no shortest s-t-path satisfies both (i) Figure 9: The three cases distinguished by Lemma 4.7 (only the vertices of a shortest path are drawn).
and (ii). Then, let P = p 0 , p 1 , . . . , p d * be a shortest s-t-path that satisfies (i) and which is chosen to minimize i > li(P ), which is the largest index such that we reverse the vertex ordering of G, swap s and t, and reverse the direction of P , then we obtain a shortest s-t-pathP satisfying (ii) but not (i). Applying the above arguments toP now yields a contradiction.
Note that the only case in which Lemma 4.6 does not restrict all vertices to be α or β vertices is when ri(P ) < li(P ), in which case Lemma 4.2 applies. This will allow us to show that, when searching for a shortest s-t-path, it is sufficient to check for three possible cases (illustrated in Fig. 9). In the following, we define the left and right horizon of a vertex v as the furthest neighbor in that direction, that is, lhorizon(v) := min(N[v]) and rhorizon(v) := max (N[v]). Remember that d * = dist(s, t). (i) β s (σ) = β t (τ ) with σ + τ = d.
Proof. For (i) and (ii), the existence of an s-t-path of length at most d follows directly from the definition of α and β. Assume now that (iii) is true. Define h v := rhorizon(v) and h w := lhorizon(w). If the edges {v, h v } and {w, h w } are crossing, then the existence of an s-t-path of length σ + τ + 3 follows from the X-property. Otherwise, let v ≤ h w ≤ s < w (the case v < t ≤ h v ≤ w is symmetric). Let P be a shortest s-v-path. Then, P either crosses the edge {w, h w } or contains w or h w . In any case, we obtain an s-w-path of length at most σ + 1 and thus an s-t-path of length at most σ + τ + 1 < d. Proof. Let P = p 0 , p 1 , . . . , p d * be a shortest s-t-path satisfying conditions (i) and (ii) as described in Lemma 4.6.
We are now ready to present our shortest path algorithm (Algorithm 1). It uses the following two definitions of the neighbors of a vertex v that are closest to another vertex a.
If the sets on the right hand side are empty, we treat these values as ∞ resp. −∞. For given vertices v and a, these two neighbors can be computed in O(log(deg(v))) time using binary search on the (sorted) adjacency list of v. It is also possible to compute them for a fixed vertex v and all other vertices a in O(n) time.
In contrast, checking condition (ii) requires slightly more effort. To test the existence of an edge {α s (i), α t (j)} with i ≤ j, we store the computed values for α s (i) in a list Q s , sorted in such a way that the vertices r i := rclosest t (α s (i)) are ordered from left to right. Whenever the iteration reaches a value j such that α t (j) is to the right of the leftmost of these r i , we have an edge of the form {α s (i), α t (j)} with i ≤ j (by the X-property). To test for edges {α s (i), α t (j)} with i ≥ j, we use a symmetrical procedure with a list Q t . Proof. We begin by showing the following invariants that are maintained throughout the computation.

14:
end if 15: if lclosest s (α t ) > lclosest s (head(Q t )) then 16: add α t to the front of Q t

17:
end if 18: end procedure Having established the above invariants, we claim that d ≤ d * holds after the for loop has reached k = d * . By Lemma 4.8, we know that one of the conditions (i)-(iii) is true.
If condition (i) is true, then there are σ and τ with σ + τ = d * and β s (σ) = β t (τ ). Then, d will be set to d * in Line 11 as soon as k reaches max{σ, τ }.
If condition (ii) is true, then there are σ and τ with σ + τ = d * − 1 such that α s (σ) and α t (τ ) are connected by an edge. As soon as k = σ, the vertex α s (σ) will be added to Q s by UpdateDistances and as soon as k = τ , the vertex α t (τ ) will be added to Q t . Therefore, when k reaches the value max{σ, τ }, then d will be set to d * either in Line 14 or Line 18 (depending on whether σ ≤ τ ).
Since d ≥ d * is an invariant, the for loop will at some point reach k = d * , and thus, Algorithm 1 outputs exactly d * . It remains to prove the running time. As shown above, the for loop is repeated at most d * + 1 times. Apart from the inner while loops, each iteration only takes constant time. Since at most one vertex is added to Q s and Q t in each of these iterations, the inner while loops are also iterated at most d * + 1 times overall.
Note that initializing all d s [v] and d t [v] with ∞ in Line 3 is only done for ease of notation. In practice, these distance values only need to be stored once they get updated by UpdateDistances.
How does the running time change if we incorporate the computation of lclosest a (v) and rclosest a (v)? Algorithm 1 requires knowledge of these values for all a ∈ {s, t} and v ∈ {α b (i), β b (i) | b ∈ {s, t}, i ≤ d * }. This amounts to O(d * ) many computations, each taking O(log(∆)) time where ∆ is the maximal degree of any vertex. The overall running time is thus in O(d * · log(∆)). Alternatively, one can precompute these values for all a, v ∈ V (G) in O(n 2 ) time and then run Algorithm 1 in output-optimal time O(d * ) for any pair s, t.
Note that even though we always assumed dist(s, t) < ∞, Algorithm 1 can easily be extended to handle the case dist(s, t) = ∞ by additionally testing whether any of the vertices α s , β s , α t , β t was updated in ExtendSearchRange. If not, then the algorithm terminates.
As a final remark, we mention that Algorithm 1 always finds a shortest s-t-path that uses only vertices in {α s (i), β s (i), α t (i), β t (i) | i ≤ dist(s, t)}.

Dominating Set on Funnel Visibility Graphs
In this section we consider the Dominating Set problem (which is a variant of the Art Gallery or Guarding problem in the context of visibility graphs) on a subclass of terrain visibility graphs called funnel (or tower [12]) visibility graphs [10].

Input:
An undirected graph G and an integer k. Question: Does G contain k vertices such that every other vertex is adjacent to at least one of them?
A funnel is a terrain that has exactly one convex vertex (called the bottom) and whose leftmost and rightmost vertex see each other 1 (see Figure 10). Funnels appear in several visibility-related tasks in geometry and their visibility graphs are linear-time recognizable [10]. Funnel visibility graphs are characterized precisely as bipartite permutation graphs with an added Hamiltonian cycle [12]. In the following, we assume to be given the graph together with the corresponding vertex coordinates of the funnel (which can be precomputed in linear time [10]).
Dominating Set is NP-hard on polygon visibility graphs [25] but it is open whether NP-hardness also holds on terrain visibility graphs. Dominating Set is solvable in linear time on permutation graphs [9], but due to the added Hamilton cycle, that approach seems not to be applicable for funnel visibility graphs. We give an O(n 4 )-time algorithm solving Dominating Set on funnel visibility graphs.
Let L = {λ 0 , . . . , λ n L } and R = {ρ 0 , . . . , ρ n R } be the vertices to the left resp. right of the bottom vertex λ 0 = ρ 0 , where L and R are ordered by increasing y-coordinate. L and R are also referred to as the two chains of the funnel. We define i(λ j ) = i(ρ j ) = j as the index of a vertex in its corresponding chain. The following observation is immediate.
We compute a minimum dominating set via dynamic programming. To this end, we first prove the following structural lemma. Otherwise (that is, i(d(ℓ) ↑ ) < r and i( ↑ d(r)) < ℓ), if d(ℓ) and d(r) are both from the same chain (say L), then i(d(ℓ)) > i(d(r)) (since otherwise i( ↑ d(r)) ≥ ℓ) and therefore i(d(ℓ) ↑ ) ≥ i(d(r) ↑ ) ≥ r, which is a contradiction.
Note that Lemma 5.2 guarantees that the above three cases are well-defined, that is, we always consider dominating sets of bases in the recursion. The recursion terminates with D(−1, −1) := ∅. To compute D(ℓ, r), we keep the minimum-size candidate set over all possible choices for x and y. Hence, a minimum dominating set D(n L , n R ) can be computed in O(n 2 · n 2 ) time.

Conclusion
Several open questions remain. Most prominently, a precise characterization of terrain visibility graphs (and their polynomial-time recognition) still remains open. This involves resolving the conjecture that terrain visibility graphs are exactly the graphs with a Hamiltonian path satisfying the X-and bar-property. It might also be interesting to give a characterization of induced subgraphs of terrain visibility graphs. Note that these clearly still satisfy the X-property for some vertex ordering, but not necessarily the barproperty. For example, it is open whether all unit interval graphs can appear as induced graphs.
As regards algorithmic questions, polynomial-time solvability of Dominating Set on terrain visibility graphs is open. One might also improve the running time for Dominating Set on funnel visibility graphs. Furthermore, a fast algorithm for finding shortest paths with respect to Euclidean distances on arbitrary induced subgraphs of terrain visibility graphs might be of interest. In general, it is worth to search for more efficient algorithms to compute graph characteristics used in practice such as clustering coefficients or centrality measures.