Exploring Increasing-Chord Paths and Trees
Yeganeh Bahoo Stephane Durocher Sahar Mehrpour Debajyoti Mondal


Large-amplitude rapid X-ray variability in the narrow-line Seyfert 1 galaxy PG 1404+226
    G. C. Dewangan
    December 30, 2023
=======================================================================================





A straight-line drawing Γ of a graph G=(V,E) is a drawing of G in the Euclidean plane, where every vertex in G is mapped to a distinct point, and every edge in G is mapped to a straight line segment between their endpoints. A path P in Γ   is called  increasing-chord if for every four points (not necessarily vertices) a,b,c,d on P  in this order, the Euclidean distance between b,c is at most the Euclidean distance between a,d. A spanning tree T rooted at some vertex r in Γ is  called increasing-chord if T contains an increasing-chord path from r to every vertex in T.   We prove that given a vertex r in a straight-line drawing Γ, it is NP-complete to decide whether Γ contains an increasing-chord spanning tree rooted at r, which answers a question posed by Mastakas and Symvonis <cit.>. We also  shed light on 
 the problem of finding an increasing-chord path between a pair of vertices in Γ, but the computational   complexity question  remains open.  




§ INTRODUCTION

  
 
In 1995, Icking et al. <cit.> introduced the concept of a self-approaching curve. A curve is called self-approaching if for any three points a, b and c on the curve in this order, |bc| ≤ |ac|, where |xy| denotes the Euclidean distance between x and y. A curve is called increasing-chord if it is self-approaching  in both directions. 
 A path P in a straight-line drawing Γ is called  increasing-chord  if for every four  points (not necessarily  vertices) a,b,c,d on P  in this order, the inequality  |bc|≤ |ad| holds. Γ is called an increasing-chord drawing if there exists an increasing-chord path between every pair of vertices in Γ.  

The study of increasing-chord drawings was motivated by greedy routing in geometric networks, where given two vertices s and t, the goal is to send a message from s to t using some greedy strategy, i.e., at each step, the next vertex in the route is selected greedily as a function of the positions of the neighbors  of the current vertex u relative to the positions of u, s, and t <cit.>. A polygonal path u_1,u_2, …, u_k is called a greedy path if for every i, where 0<i<k, the inequality |u_iu_k| > |u_i+1u_k| holds. If a straight-line drawing is greedy, i.e., there exists a greedy path between every pair of vertices, then it is straightforward to route the message between any pair of vertices by  following a    greedy path. For example, we  can repeatedly forward the message to some node which is closer to the destination than the current vertex. A disadvantage of a greedy drawing, however, is that the dilation, i.e., the ratio of the graph distance to the Euclidean distance  between a pair of vertices, may  be unbounded.  Increasing-chord drawings were introduced to address this problem, where the dilation of increasing-chord drawings can be at most 2 π /3 ≤ 2.094 <cit.>. 

 Alamdari et al. <cit.> examined the problem   of recognizing increasing-chord drawings, and the problem of constructing  such a drawing on a given set of points.  They showed that it is NP-hard to recognize increasing-chord drawings in ℝ^3, and asked whether it is also NP-hard in ℝ^2. They also proved that for every  set of n points P in ℝ^2, one can  construct an increasing-chord drawing Γ with O(n)  vertices and edges, where P is a subset of the vertices of Γ. In this case, Γ is called a Steiner network of P, and the vertices of Γ that do not belong to P are called Steiner points. Dehkordi et al. <cit.> proved that if P is a convex point set, then one can construct an increasing-chord network  with  O(nlog n) edges, and without introducing any Steiner point. 
 Mastakas and Symvonis <cit.> improved the O(nlog n) upper bound on edges to O(n) with at most one Steiner point. Nöllenburg et al. <cit.> examined the problem of computing increasing-chord drawings of given graphs. 
 Recently, Bonichon et al. <cit.> showed that the existence of an angle-monotone path of width 0≤γ<180^∘     between a pair of vertices (in a straight-line drawing) can be decided in polynomial time, which is very interesting since angle-monotone paths of width γ≤ 90^∘ satisfy increasing chord property.  
 


Nöllenburg et al. <cit.> showed that partitioning a plane graph drawing
 into a minimum number of increasing-chord components is NP-hard, which extends a result of Tan and
Kermarrec <cit.>. They also proved that the problem remains NP-hard for trees, and gave
 polynomial-time algorithms in some restricted settings. 
 Recently, Mastakas and Symvonis <cit.> showed that given a point set S and a point v∈ S,  one can compute a rooted minimum-cost spanning tree in polynomial time, where each point in S∖{v} is connected to v by a path that satisfies  some monotonicity property. They also proved that the existence of a monotone rooted spanning tree in a given geometric graph can be decided in polynomial time, and asked whether the decision problem remains NP-hard also for increasing-chord or self-approaching properties. 


 








 

We prove that given a vertex r in a straight-line drawing Γ, it is NP-complete to decide whether Γ contains an increasing-chord spanning tree rooted at r, which answers the above question. We also  shed light on the problem of finding an increasing-chord path between a pair of vertices in Γ, but the computational   complexity question  remains open.  
  


§ TECHNICAL BACKGROUND



 


Given a straight line segment l, the slab of l is an infinite region lying between a pair of parallel straight lines that are perpendicular to l, and pass through the endpoints of l.  Let Γ be a straight-line drawing, and let P be a path in Γ. Then the slabs of P are the slabs of the line segments of P. We denote by Ψ(P) the arrangement of the slabs of P. Figure <ref>(a) illustrates a path P, where the slabs of P are shown in shaded regions. Let A be an arrangement of a set of straight lines such that no line in A is vertical. Then the upper envelope  of A is a polygonal chain U(A) such that each point of U(A) belongs to some straight line of A, and  they are visible from the point (0,+∞). The upper envelope of a set of slabs is the upper envelope of the arrangement of lines corresponding to the slab boundaries, as shown in dashed line in Figure <ref>(a). 



Let t be a vertex in Γ and let Q=(a,b,…,p) be an increasing-chord path in Γ. A path Q'=(a,b,…,p,…,t) in Γ is called an increasing-chord extension of Q if Q' is also an increasing-chord path,  e.g., see Figure <ref>(b).  The following property can be derived from the definition of an increasing-chord path.



[Icking et al. <cit.>]

A polygonal path P is increasing-chord if and only if for each point v on the path, the line perpendicular to P at v does not  properly intersect  P except possibly at v. 



A straightforward consequence of Observation <ref> is that every polygonal chain which is both x- and y-monotone, is an increasing-chord path.  We will use Observation <ref> throughout the paper to verify whether a path is increasing-chord.  Let v be a point in ℝ^2. By the quadrants of v we refer to the four regions determined by the vertical and horizontal lines through v. 


  


§ INCREASING-CHORD ROOTED SPANNING TREES




In this section we prove the problem of computing a rooted increasing-chord
 spanning tree of a given straight-line drawing to be NP-hard. We will refer to this 
 problem as IC-Tree, as follows:



  Problem: Increasing-Chord Rooted Spanning Tree (IC-Tree)

  Instance: A straight-line drawing Γ in ℝ^2, and a vertex r in Γ.

  Question: Determine whether Γ contains a tree T rooted at r such that for each vertex v(≠ r) in Γ, T contains an increasing-chord path between r and v. 

Specifically, we will prove the following theorem. 


Given a vertex r in a straight-line drawing Γ, it is NP-complete  to decide whether Γ admits an increasing-chord spanning tree rooted at r. 


 
 


 We reduce the NP-complete problem 3-SAT <cit.> to IC-Tree.  Let I=(X,C) be an instance of 3-SAT, where X and C are the set of variables and clauses. We construct a straight-line drawing Γ and choose a vertex r in Γ such that Γ contains an increasing-chord spanning tree rooted at r if and only if I admits a satisfying truth assignment.
 Here we give an outline of the hardness proof and describe the construction of Γ. 
 A detailed reduction is given in Appendix B. 




Assume that α = |X|, and β = |C|. Let l_h be the line determined by the X-axis. Γ will contain  O(β) points above l_h, one point t on l_h, and  O(α) points below l_h, as shown in Figures <ref>(a)–(b).  Each clause c∈ C with j literals, will correspond to a set of j+1 points above l_h, and we will refer to the point with the highest y-coordinate among these j+1 points as the peak t_c of c. Among the points below l_h, there are 4α points that correspond to the variables and their negations, and  two other points, i.e., s  and r. In the reduction, the point t and the points below l_h altogether help to set the truth assignments of the variables.  
 
We will first create a straight-line drawing H such that  every increasing-chord path between r and t_c, where c∈ C, passes through s and t. Consequently, any increasing-chord tree T rooted at r (not necessarily spanning), which spans the points   t_c, must contain an increasing-chord path P=(r,s,…,t). We will use this path to set the truth values of the variables. 

The edges of H below l_h will create a set of thin slabs, and the upper envelope of these slabs will determine a convex chain W above l_h. Each line segment on W will correspond to a distinct variable, as shown in Figure <ref>(b). 
 The points that correspond to the clauses will be positioned below these segments, and hence 
 some of these points will be `inaccessible' depending on the choice of the path P. 
 These literal-points will ensure that for any clause c∈ C, there exists
 an increasing-chord extension of P from t to  t_c if and only if c
 is satisfied by the truth assignment determined by P.


By the above discussion, I admits a satisfying truth assignment if and only if there exists an increasing-chord tree T in H that connects the peaks to r. But H may still contain some vertices that do not belong to this tree. Therefore, we construct the final drawing Γ by adding some new paths to H, which will allow us to reach these remaining vertices  from r. 
 We now describe the construction in details. 



Construction of H:   
 We first construct an arrangement 𝒜 of 2α straight line segments.  The endpoints of the ith line segment L_i, where 1≤ i≤ 2α, are (0,i) and (2α-i+1,0). We now extend each L_i downward by scaling its length by a factor of (2α+1), as shown in Figure <ref>(a). Later, the variable x_j, where 1≤ j≤α, and its negation  will be represented using the lines L_2j-1 and L_2j.   
Let l_v be a vertical line segment with endpoints (2α+1,2α) and (2α+1,-5α^2). Since the  slope of a line in 𝒜 is in the interval [-2α, - 1/(2α)], each L_i intersects l_v.  Since the coordinates of the endpoints of L_i and l_v are of size O(α^2), and all the intersection points can be represented using polynomial space.

 

By construction, the line segments of 𝒜 appear on  U(𝒜) in the order of the variables, i.e., the first two segments (from right) of   U(𝒜) correspond to x_1 and x_1, the next two segments correspond to x_2 and x_2, etc.




Variable Gadgets: 
 
 We denote the intersection point of l_h and l_v  by t, and the   endpoint (2α+1, - 5α^2) of l_v by s. 
 We now create the points that correspond to the variables and their negations. Recall that L_2j-1 and L_2j correspond to the variable x_j and its negation x_j, respectively. Denote the intersection point of L_2j-1 and l_v by p_x_j, and the intersection point of L_2j and l_v by p_x_j, e.g., see  Figure <ref>(b). For each p_x_j
 (p_x_j), we create a new point p'_x_j (p'_x_j) such that the straight line segment
 p_x_jp'_x_j (p_x_jp'_x_j) is perpendicular to L_2j-1 (L_2j), as shown using the dotted (dashed) line  in Figure <ref>(b). 
 
  We may assume that all the points p'_x_j and p'_x_j lie on a vertical line l'_v, where l'_v lies ε distance away to the left of l_v. The value of ε would be determined later. In the following we use the points p_x_j, p_x_j, p'_x_j and p'_x_j to create some polygonal paths from s to t. 

For each j from 1 to α,  we draw the  straight line segments p_x_jp'_x_j and  p_x_jp'_x_j. Then for each k,  where 1< k ≤α, we make   p_x_k and p_x_k adjacent  to both p'_x_k-1 and p'_x_k-1,  e.g., see Figure <ref>(c). We then add the edges from s to p'_x_α and p'_x_α, and finally, from t to p_x_1 and p_x_1. For each x_j
 (x_j), we refer to the segment p_x_jp'_x_j (p_x_jp'_x_j) as the needle of x_j (x_j). Figure <ref>(c) illustrates the needles in bold.
 Let the resulting drawing be H_b. 


Recall that l'_v is ε distance away to the left of l_v. We choose ε sufficiently small such that for each needle, its slab does not intersect any other needle in H_b, e.g., see Figure <ref>(d).  The upper envelope of the slabs of all the straight line segments of H_b coincides with U(𝒜). Since the distance between any pair of points that we created on l_v is at least 1/α units, it suffices to choose ε = 1/α^3. Note that the points p'_x_j and p'_x_j can be represented in polynomial space using the endpoints of l'_v and the endpoints of the segments  L_2j-1 and L_2j. 
 The proof of the following lemma is included in   Appendix A.
  


Every increasing-chord path P that starts at s and ends at t must pass through exactly one point among p_x_j and p_x_j, where 1 ≤ j≤α, and vice versa.

 
 
We now place a point r on the y-axis sufficiently below H_b, e.g., at position (0,-α^5), such that the slab of the straight line segment rs does not intersect H_b (except at s), and similarly, the slabs of the line segments of H_b do not intersect rs. 
 Furthermore, the slab of rs does not intersect any segment L_j, and vice versa.  We then add the point r and the segment rs to H_b. Let P be an increasing-chord path from r to t. The upper envelope of Ψ(P)   is determined by the needles in P, which selects some segments from the convex chain W, e.g., see Figure <ref>(b). For each x_j, P passes through exactly one point among p_x_j and p_x_j. Therefore, for each variable x_j, either the slab of x_j, or the slab of x_j  appears on U(P).  Later, if P passes through point p_x_j (p_x_j), then we will set x_j to false (true). Since P is an increasing-chord path, by Lemma <ref> it cannot pass through both  p_x_j and  p_x_j simultaneously. Therefore, all the truth values will be set consistently.



Clause Gadgets: 
We now complete the construction of H by adding clause gadgets to H_b. For each clause c_i, where 1≤ i≤β, we first create the peak point t_c_i at position (0,2α+i). For each variable x_j, let λ_x_j  be the interval of L_2j-1 that appears  on the upper envelope of 𝒜. Similarly, let λ_x_j be the  interval of  L_2j   on the upper envelope of 𝒜.  For each c_i, we  construct a point q_x_j,c_i (q_x_j,c_i) inside the cell of 𝒜  immediately below   λ_x_j (λ_x_j).   We will refer to these points as the literal-points of   c_i.  Figure <ref> in  Appendix B depicts these points in black squares. 
 We assume that for each variable, the corresponding literal-points 
 lie on the same location. One may perturb them to remove vertex overlaps. 
 For each variable x∈ c_i, we create a path (t, x, t_c).  
 
 
 In the reduction, if at least one of the literals of  c_i is true, 
 then we can take the corresponding path
 to connect t_c to t. Let the resulting drawing be H. 






Construction of Γ:   
 Let q be a literal-point in H. We now add an increasing-chord path  P' = (r,a,q) to H in such a way that P' cannot be extended to any larger increasing-chord path in H. We place the point a at the intersection point of the horizontal line through q and the  vertical line through r, e.g., see Figure <ref>(b) in Appendix B. We refer to the point a as the anchor of q.  By the construction of H, all the neighbors of q that have a higher y-coordinate than q lie in the top-left quadrant of q, as illustrated by the  dashed rectangle in Figure <ref>(b).  Let q' be the first neighbor in the top-left quadrant of q in counter   clockwise order. Since ∠ aqq'< 90^∘, P' cannot be extended to any larger increasing-chord path (r,a,q,w) in H, where the y-coordinate of w is higher than q.  On the other hand, every   literal-point w in H with y-coordinate smaller than q intersects the slab of ra. Therefore, P' cannot be extended to any larger increasing-chord path. 

For every literal-point q in H, we add such an increasing-chord path from t to q. To avoid edge overlaps, one can  perturb the anchors such that  the new paths remain  increasing-chord and non-extensible to any larger increasing-chord paths. This completes the construction of Γ. We refer the reader to Appendix B for the  formal details of the reduction.


 
 


§ INCREASING-CHORD PATHS



In this section we attempt to reduce 3-SAT to the problem of finding an increasing-chord path (IC-Path) between a pair of vertices in a given straight-line drawing. 
 We were unable to bound the coordinates of the drawing to a polynomial number of bits, and hence the computational complexity question of the problem remains open. We hope that the ideas we present here will be useful in future endeavors to settle the question.






  
Here we briefly describe the idea of the reduction. Given a 3-SAT instance I=(X,C),  the corresponding drawing  for IC-Path consists of straight-line drawings _i-1, where 1≤ i≤β, e.g., see Figure <ref>(a). The drawing _i-1 corresponds to the each clause c_i. We will refer to the bottommost (topmost) point of _i-1 as t_c_i-1 (t_c_i). We will choose t_c_0 and t_c_β to be the points t and t', respectively, and show that I admits a satisfying truth assignment if and only if there exists an  increasing-chord  path P from t to t' that passes through every  t_c_i. For every i, the subpath P_i-1 of P between t_c_i-1 and  t_c_i will correspond to a set of truth values for all the variables in X. The most involved part is to show that the truth values determined by P_i-1 and P_i are consistent. This consistency will be ensured by the construction of , i.e.,   the increasing-chord path P_i-1 from t_c_i-1 to t_c_i in _i-1 will determine a set of slabs, which will force a unique increasing-chord path P_i in _i between t_c_i and t_c_i+1 with the same truth values as determined by P_i-1.   



Construction of : 

 
 The construction of _i-1 depends on an arrangement of lines 𝒜^i-1. The construction of 𝒜^0 is the same as the construction of arrangement 𝒜, which we described in Section <ref>.  Figure <ref>(c) illustrates 𝒜^0 in dotted lines.  For each variable x_j, where 1≤ j ≤α, there exists an interval λ^0_x_j of L_2j-1 on the upper envelope of 𝒜^0. Similarly, for each   x_j,  there exists an interval λ^0_x_j of L_2j on the upper envelope of 𝒜^0.  










 
We now describe the construction of _0. Choose t_c_0 (t_c_1) to be the bottommost (topmost)   point of λ^0_x_1 (λ^0_x_α). We then slightly shrink the intervals  
 λ^0_x_1 and λ^0_x_α such that t_c_0 and  t_c_1 no longer belong to these segments.  Assume that c_1  contains δ literals, where δ≤ 3, and let   σ_1,…,σ_2^δ -1 be the satisfying truth assignments for c_1. We construct a graph G_c_1 that corresponds to these satisfying truth assignments,  e.g., see Figure <ref>(b) and Appendix C for formal details. The idea is to ensure that any path between t_c_0 and t_c_1 passes through exactly one point in {q^σ_k_x_j, q^σ_k_x_j}, for each truth assignment σ_k, which will set the truth value of x_j.  In 𝒟_0, the point  q^σ_k_x_j (q^σ_k_x_j) is chosen to be the midpoint of λ^i-1_x_j (λ^i-1_x_j). Later, we will refer to these points as q-points, e.g., see Figure <ref>(c).  We may assume that for each x_j, the points q^σ_k_x_j lie at the same location. At the end of the construction, one may perturb them to remove vertex overlaps.



 
By Observation <ref>, any y-monotone path P' between t_c_0 and t_c_1 must be an increasing-chord path.  
 If P' passes through  q^σ_x_j, then we set x_j to true. Otherwise, P' must pass through   q^σ_x_j,
 and we set x_j to false.
 In the following we replace each q-point by a small segment. The slabs of these segments will determine 𝒜^1.  Consider an upward ray r^1 with positive slope starting at the q-point on λ_x_1, e.g., see Figure <ref>(c). Since all the edges that are currently in _0 have negative slopes, we can choose a sufficiently large positive slope for r^1 
 and a point a^1 on r^1 such that all the slabs of _0 lie below a^1.
 We now find a point b^1 above a^1 on r^1 with sufficiently large y-coordinate
 such that the slab of t_c_1b^1 does not intersect the edges in _0.  
 Let l^1_x_1 be the line determined by r^1. 
 For each x_j and x_j  (except for j=1), we now construct the lines  l^1_x_j and l^1_x_j  that pass through their corresponding q-points and intersect r^1 above b^1.
 The lines l^1_x_j and l^1_x_j determine the arrangement 𝒜^1. 
 Observe that one can construct these lines in the decreasing order of 
 the x-coordinates of their q-points, and ensure that 
 for each  l^1_x_j (l^1_x_j), there exists an interval λ^1_x_j
 (λ^1_x_j) on the upper envelop of 𝒜^1.
 Note that the correspondence is inverted, i.e.,  in 𝒜^1, λ^1_x_j corresponds
 to λ^0_x_j, and  λ^1_x_j corresponds to λ^0_x_j.
 
 
For each   j, we draw a small  segment 
   s^0_x_j (s^0_x_j) perpendicular to l^1_x_j (l^1_x_j)
   that passes through the q-point and lies to the left of q, e.g., see  Figure <ref>(d).  
  
     
   
   
   
   
   
 The construction of _i, where i>1, is more involved. 
 
 The upper envelope of 𝒜^i+1 
 is determined by the upper envelope of the   slabs of the s-segments in  _i-1. For each i, we 
 construct the q-points and corresponding graph G_c_i. Appendix C includes the formal details. 

In the reduction we show that  any increasing-chord path P from t to t' contains the points t_c_i.  We set a variable x_j true or false depending on whether  P passes through s^0_x_j or s^0_x_j.   The construction of  imposes the constraint that if P passes through  s^i-1_x_j (s^i-1_x_j), then it must pass through s^i_x_j (s^i_x_j). Hence the truth values in all the clauses are set consistently. By construction of G_c_i, any increasing-chord path between t_c_i-1 to t_c_i determines a satisfying truth assignment for c_i.  
 On the other hand, if I admits a satisfying truth assignment, then for each clause c_i, we choose the corresponding increasing-chord path P_i between t_c_i-1 and t_c_i. The union of all P_i yields the required increasing-chord path P from t to t'. Appendix C presents the construction in details, and explains the challenges of encoding  in a polynomial number of bits.





§ OPEN PROBLEMS



 The most intriguing problem in this context is to settle the computational complexity 
 of the increasing-chord path (IC-Path) problem. 
 Another interesting question is whether the problem IC-Tree remains NP-hard under the planarity
 constraint; a potential attempt to adapt our hardness reduction could be replacing the edge intersections by dummy vertices. 








abbrv
 
 






§ APPENDIX A




    < g r a p h i c s >
 
figureIllustration for the hardness proof using a schematic representation of Γ. The points that correspond to c_1 and c_2 are connected in paths of  black, and lightgray, respectively.  The slabs of the edges of H that determine the upper envelope are shown in lightgray straight lines. Each variable and its negation correspond to a pair of adjacent line segments on the upper envelope of  the slabs. 
  







Lemma <ref>
 Every increasing-chord path P that starts at s and ends at t must pass through exactly one point among p_x_j and p_x_j, where 1 ≤ j≤α, and vice versa.

By Observation <ref>,  P must be y-monotone. Consequently, for each j, the edge on the (2j)th position on P is a needle, which corresponds to either  p_x_jp'_x_j or p_x_jp'_x_j. Therefore, it is straightforward to observe that P passes through exactly one point among p_x_j and p_x_j. 

Now consider a path P that  starts at s, ends at t,  and for each j,  
 passes through exactly one point among p_x_j and p_x_j. 
 By construction, P must be y-monotone. 
 We now show that  P is an increasing-chord path. Note that
 it suffices to show that for every straight-line segment ℓ on P,
 the slab of ℓ does not properly intersect P except at ℓ. 
 By Observation <ref>, it will follow that P is an increasing-chord path.

For every interior edge e on P, which is not a needle, e corresponds to some segment ℓ∈{
p_x_jp'_x_j-1, p_x_jp'_x_j-1
p_x_jp'_x_j-1, p_x_jp'_x_j-1}, for some 1<j≤α. By construction, in each of these four cases,
 the needles incident to  ℓ lie either on the boundary or entirely outside of the
 the slab of ℓ, and hence the slab does not properly intersect P except at ℓ.  
  Figures <ref>(a)–(b) illustrate the scenario when ℓ∈{ 
p_x_jp'_x_j-1, p_x_jp'_x_j-1}. 


Let (s,a) and (b,t) be the edges on P incident to s and t, respectively.
 By construction, these edges behave in the same way, i.e., all the needles on P 
 are above the slab of (s,a) and below the slab of (b,t). 
 Consequently, the slab of (s,a) (resp., (b,t)) does not properly intersect P except at
 (s,a) (resp., (b,t)).
 
For every interior edge e on P, which is a needle, e corresponds to some segment ℓ∈{
p_x_jp'_x_j,  p_x_jp'_x_j}. By construction, the needles following (resp., preceding) ℓ on P 
 are above (resp., below) the slab of ℓ.  Consequently, the
  slab does not properly intersect P except at ℓ.  
  Figures <ref>(c)–(d) illustrate these scenarios.  
  




    < g r a p h i c s >
 
figureIllustration for the slab of ℓ. (a)–(b) The segment ℓ is not a needle.
(c)–(d) The segment ℓ is   a needle.
  






 



§ APPENDIX B











    < g r a p h i c s >
 
figure(a) Construction of clause gadgets, where c_1 = (x_1∨ x_3).
 (b) A schematic representation of Γ. (c) Illustration for the reduction.
  





Since determining whether a straight-line drawing of a tree  is an increasing-chord drawing is polynomial-time solvable <cit.>, the problem IC-Tree is NP-complete. 
 We  now prove that Γ  admits an  increasing-chord rooted spanning tree if and only if I admits a satisfying truth assignment.

 

Equivalence between the instances:    
 First assume that I admits a satisfying truth assignment. We now construct an increasing-chord spanning tree T rooted at r. We first choose a path P from r to t such that it passes through either p_x_j or p_x_j, i.e., if x_j is true (false), then we route the path through p_x_j (p_x_j). Figure <ref>(c) illustrates such a path P in a thick black line, where x_α=  true and  x_α-1=  false. 

Observe that only 2α points remain below l_h, two points per literal, that do not belong to P. We connect these points in a y-monotone polygonal path Q starting  at s, as illustrated in a thin black line in Figure <ref>(c). Note that Q corresponds to a truth value assignment, which is opposite to the truth values determined by P. Therefore, by Lemma <ref>, Q is also an increasing-chord path. Consequently, the point t and the   points that lie below l_h are now connected to r through  increasing-chord paths. 

The tree T now consists of the paths P and Q, and thus does not span the vertices that lie above l_h. We now add  more paths to T to span the points above l_h. Since every clause c is satisfied,  
 we can choose a path  P'  from t to t_c that passes through 
 a literal-point  whose corresponding literal x∈ c is true.  Since  the  literal-points corresponding to
 true literals lie above  the slabs of P,   the path P' determines an increasing-chord extension of P. Therefore, all the peaks and some literal-points above l_h are now connected to r via increasing-chord paths.  

For each remaining literal-point q, we add q to T via the increasing-chord path through its anchor. There are still some anchors that are not connected to r, i.e., the anchors   whose corresponding literal-points are already connected to r via an increasing-chord extension of P. We connect each  anchor a to r via the straight line segment ar.  




We now assume that Γ contains an increasing-chord rooted spanning tree T, and show how to find  a satisfying   truth assignment for I. Since T is rooted at r, and the peaks are not reachable via anchors, T must contain an increasing-chord path P = (r,s,…,t) that for each variable x_j, passes through exactly one point among p_x_j and p_x_j. If P passes through p_x_j  (p_x_j), then we set x_j    to false (true).  Observe that passing through a variable x_j or its negation selects a corresponding needle segment p'_x_jp_x_j or p'_x_jp_x_j.  
 Recall that the interval λ_x_j (λ_x_j), which  corresponds to
  p'_x_jp_x_j (p'_x_jp_x_j), lies above the literal-point
 q_x_j,c_i (q_x_j,c_i), e.g.,
 see Figure <ref>(a).  
  Therefore, if the above truth assignment does not satisfy some clause c, then there cannot be any increasing-chord extension of P that connects t to t_c. Therefore, T would not be a  spanning tree.  


 


§ APPENDIX C


Here we give the formal details of the construction of .

Construction of _0: 
 Choose t_c_0 (t_c_1) to be the bottommost (topmost)   point of λ^0_x_1 (λ^0_x_α). We then slightly shrink the intervals  
 λ^0_x_1 and λ^0_x_α such that t_c_0 and  t_c_1 no longer belong to these segments.  If c_1  contains κ literals, then there are 2^κ -1 distinct truth assignment for its variables to satisfy c_1. For each satisfying truth assignment σ_k, where 1≤ k ≤ 2^κ -1, we construct a set of vertices and edges in _0, as follows.
 For each x_j (x_j), we construct a point q^σ_k_x_j (q^σ_k_x_j) at the midpoint of λ^i-1_x_j (λ^i-1_x_j). Later, we will refer to these points as q-points, e.g., see Figure <ref>(c). 
 For each  j from 1 to (α-1), we make  q^σ_k_x_j and q^σ_k_x_j adjacent to q^σ_k_x_j+1, q^σ_k_x_j+1, e.g., see Figure <ref>(b). We then make t_c_0 (t_c_1) adjacent to the points corresponding to x_1 (x_α) and its negation. Finally,  if  x_j (resp., x_j) is true in σ_k, then we remove the edges incident to q^σ_k_x_j (resp., q^σ_k_x_j).  We may assume that for each x_j, the points q^σ_k_x_j lie at the same location. At the end of the construction, one may perturb them to remove vertex overlaps.


By Observation <ref>, any y-monotone path P' between t_c_0 and t_c_1 must be an increasing-chord path.  
 If P' passes through  q^σ_x_j, then we set x_j to true. Otherwise, P' must pass through   q^σ_x_j,
 and we set x_j to false.
 In the following we replace each q-point by a small segment. The slabs of these segments will determine 𝒜^1.  Consider an upward ray r^1 with positive slope starting at the q-point on λ_x_1, e.g., see Figure <ref>(c). Since all the edges that are currently in _0 have negative slopes, we can choose a sufficiently large positive slope for r^1 
 and a point a^1 on r^1 such that all the slabs of _0 lie below a^1.
 We now find a point b^1 above a^1 on r^1 with sufficiently large y-coordinate
 such that the slab of t_c_1b^1 does not intersect the edges in _0.  
 Let l^1_x_1 be the line determined by r^1. 
 For each x_j and x_j  (except for j=1), we now construct the lines  l^1_x_j and l^1_x_j  that pass through their corresponding q-points and intersect r^1 above b^1.
 The lines l^1_x_j and l^1_x_j determine the arrangement 𝒜^1. 
 Observe that one can construct these lines in the decreasing order of 
 the x-coordinates of their q-points, and ensure that 
 for each  l^1_x_j (l^1_x_j), there exists an interval λ^1_x_j
 (λ^1_x_j) on the upper envelop of 𝒜^1.
 Note that the correspondence is inverted, i.e.,  in 𝒜^1, λ^1_x_j corresponds
 to λ^0_x_j, and  λ^1_x_j corresponds to λ^0_x_j.
 
 
For each   j, we draw a small  segment 
   s^0_x_j (s^0_x_j) perpendicular to l^1_x_j (l^1_x_j)
   that passes through the q-point and lies to the left of q, e.g., see  Figure <ref>(d).  
  We will refer to these segments as the s-segments. 
     We choose the length of the s-segments small enough such that the slabs of these segments 
   still behave as lines of 𝒜^1. 
   For each s-segment qq', if there exists an edge (w,q), where w has a larger y-coordinate 
   than q, then then we delete the segment wq and  add the line segment wq'.
   Since the slopes of the s-segments are negative,
   it is straightforward to verify that any y-monotone path between t_c_0 and t_c_1 will 
   be an increasing-chord path. 
   
This completes the construction of _0 and 𝒜^1. 

Construction of _i, where i>0: 
  The construction for the subsequent drawing _i depends on  𝒜^i,
  where 1≤ i < β, and the arrangement 𝒜^i+1 is determined
  by _i. Although the construction of _i from 𝒜^i is similar
  to the construction of _0 from 𝒜^0, we need   
  _i to satisfy some further conditions, as follows. 
	
	



 
  
  (A) In 𝒜^i+1, the segment λ^i+1_x_j (resp., λ^i+1_x_j) 
  plays the role of λ^i_x_j (resp., λ^i_x_j). 
  Therefore, the q-vertices and edges of _i 
  must be constructed accordingly. 
  As a consequence, if an increasing-chord path P' between t_c_i-1 and t_c_i passes through 
  some s^i-1_x_j (s^i-1_x_j) in _i-1, then any increasing-chord extension of
  P' to t_c_i+1 must pass through s^i_x_j (s^i_x_j) in _i.   
  
  
  (B) While constructing  _i, we must ensure that the slabs of the 
   segments in _i do not intersect the segments in _0,…,_i-1. 
   We now describe how to construct such a drawing _i, e.g., see Figure <ref>. 
   Without loss of generality assume that i is odd. The construction when 
   i is even is symmetric. Let Δ_i-1 be the largest  
   x-coordinate among all the vertices in _0,…,_i-1.
   
   Recall that the drawing of _i depends on  𝒜^i, and we construct
    𝒜^i starting with an upward ray r^i and choosing a point 
    b^i on r^i. We choose a positive slope for r^i, which is 
    larger than all the positive slopes determined by the slabs of _0,…,_i-1.
    We then choose 
    
    b^i with a sufficiently large y-coordinate such that  
    the x-coordinate of b_i is larger than Δ_i-1. It is now straightforward to 
    choose the lines of 𝒜^i such that their intersection points  
    are close to b_i, and have x-coordinates larger than Δ_i-1. 
    Since the segments of _i will have positive slopes, their slabs 
    cannot intersect the segments of _0,…,_i-1.  
  


On the size of vertex coordinates: 
  Note that  has only  a polynomial 
 number of vertices, and our incremental construction for  is straightforward
 to carry out in polynomial number of steps. Therefore, the crucial challenge  is to 
 prove whether the vertices in  can be expressed in a polynomial number of bits or not. 
 
 As explained in the description of the construction of _0, 
 observe that the width and height of _0 is O(α), where α = |X|.
 To construct _1, the crucial step is to choose the slope for r^1 and the point 
 b^1 on r^1. Since the largest slope of the slabs of 𝒜^1 is O(α),
 it suffices to choose a slope of α^3 for r^1. It is then straightforward  to choose a point 
 on r^1 as b^1, where x and y-coordinates of b^1 are 
 of size O(α) and O(α^3), respectively, e.g., see Figure <ref>(a).
 Similarly, to construct _i from _i-1, we can choose a slope of α^2i+1 
 for r^i, as illustrated in  Figure <ref>(b).
 Consequently, after β steps, where β = |C|, the width of the drawing becomes
 O(α·β) and the height becomes α^O(β). Note that we can describe  
 r^i and b^i in O(βlogα) bits.  However, encoding of the rest of
 the drawing seems difficult. For example, one can attempt to construct the 
 remaining vertices and edges of  using r^i and b^i, as follows. 
 
 


 Consider the upper envelope U(𝒜^0) of 𝒜^0. 
 To construct the straight lines for 𝒜^1, one can construct 
 a set of variables and express the necessary constraints in a non-linear programming. Specifically, for each 
 q-point q^σ_x on U(𝒜^0), we create a variable point v
 on r^1  above b^1, and a variable v' on the line
 vq^σ_x on U(𝒜^1), where the variable 
 v' corresponds to the q-point on U(𝒜^1).
 An example is illustrated in Figure <ref>.
 Similarly, for each i>1, we can create variables for the q-points of
 𝒜^i from 𝒜^i-1, r^i and b^i.
 Since the number of vertices and edges of  is polynomial,
 the constraints we need to satisfy among all these q points
 is polynomial. However, the solution size of such a nonlinear 
 system may not be bounded to a polynomial number of bits. 
 
 

Equivalence between the instances: 
Any increasing-chord path P from t to t' contains the points t_c_i.  We set a variable x_j true or false depending on whether  P passes through s^0_x_j or s^0_x_j.  By Condition (A), if P passes through  s^i-1_x_j (s^i-1_x_j), then it must pass through s^i_x_j (s^i_x_j). Hence the truth values in all the clauses are set consistently. By construction of , any increasing-chord path between t_c_i-1 to t_c_i determines a satisfying truth assignment for c_i. Hence the truth assignment satisfies all the clauses in C. 

On the other hand, if I admits a satisfying truth assignment, then for each clause c_i, we choose the corresponding increasing-chord path P_i between t_c_i-1 and t_c_i. Let P be the union of all P_i.  By construction of , the slabs of P_i do not intersect P except at P_i. Hence, P is the required increasing-chord path  from t to t'. 


 
 


