1 Introduction
Labeling problems appear in a variety of scenarios such as in annotating educational diagrams, wiring schematics, system manuals, as well as in many engineering and information visualization applications [17, 11, 9, 2]. The increasing trend of automation in these areas has motivated the research in labeling algorithms. Crossings among the leaders (i.e., the lines connecting labels to the sites), number of bends per leader, and the sum of leader lengths are some important aesthetics of a diagram labeling. To achieve clarity and better readability, all these parameters are often preferred to be kept small.
Many labeling problems are NPhard [11, 4]
. A rich body of research attempts to develop efficient approximation and heuristic algorithms
[12, 13, 8, 18, 19], both in the static and the dynamic settings [2, 8]. In this paper we examine a wellknown variant of the labeling problem called bend sided boundary labeling, e.g., see Figure 1. The input for this problem is a set of sites and ports, where the sites lie in the interior of a rectangle , the ports are located on consecutive sides of , and each side contains ports. Both the sites and ports are represented as points. The goal is to decide whether each site can be connected to a unique port using axisaligned leaders such that the leaders are disjoint, each leader lies strictly inside and each leader has at most bends. If such a labeling exists, then we compute a labeling that optimizes these labeling aesthetics. We examine two such optimization criteria: one is to minimize the sum of the leader lengths, and the other is to minimize the total number of bends.The strictcontainment inside , bend restrictions and orthogonal constraints impose certain shapes on the leader. An orthogonal leader containing exactly one bend (resp., 2 bends) is known as a leader (resp., an leader)^{2}^{2}2The letters ‘o’ and ‘p’ stands for ‘orthogonal’ and ‘parallel’, respectively. Therefore, an leader starts orthogonally at the site, and ends orthogonally at the port..
Related Work:
Boundary labeling has been an active area of research in the last decade, e.g., see the surveys [1, 17]. The boundary labeling problem was first introduced by Bekos et al. [5]. They gave time algorithms to decide labeling feasibility for the 1bend 1sided and opposite 2sided models, i.e., the labels are located on two opposite sides of . In addition, they gave an time algorithm that minimizes the total leader length. For the 2bend 4sided model, they could test the feasibility in time and reduced the length minimization to a minimumcost bipartite matching problem. Benkert et al. [6] improved Bekos et al.’s [5] result on the 1bend 1sided model by devising an time algorithm for the length minimization. They also considered general cost functions (i.e., beyond Euclidean length), as well as other types of leaders. We refer the reader to [16, 3] for other variants of boundary labeling problem.
The 2sided model considered by Bekos et al. [5] and Benkert et al. [6] is an oppositesided model, i.e., ports are placed on two opposite sides of . This model is different from the adjacent 2sided model, where the labels are always placed on adjacent sides. The adjacent 2sided model was first considered by Kindermann et al. [15]. For the 1bend 2sided model, they gave an time algorithm to check feasibility, and an time algorithm for total leader length minimization; to our knowledge, this is the fastest algorithm known for the 1bend 2sided model. Note that the labeling problem in this model seems surprisingly more difficult than the corresponding opposite 2sided model (also mentioned by Kindermann et al. [15]). For the 1bend 3sided (resp., 4sided) model, they gave an time (resp., time) algorithm for checking the labeling feasibility, but they were unable to solve the length minimization problem. They posed this as an open question, i.e., can a minimumlength solution for the 3 and 4sided boundary labeling be computed in polynomial time? These challenges motivated us to examine the adjacent model in more detail.
Fink and Suri [10] studied the boundary labeling problem in the presence of obstacles. In addition to the set of sites, they allowed a set of orthogonal polygons (equivalently, obstacles) to lie inside . The objective is to minimize the total leader length with the constraint that the leaders must not intersect the obstacles. They gave polynomialtime algorithms for minimizing the total leader length in the 1sided and opposite 2sided models, but the running time of these algorithms while using  and leaders is fairly high, i.e., , for the 1sided model, and , for the opposite 2sided model. They also examined the case when the leaders have nonuniform lengths and the leader locations can be chosen, which they proved to be NPhard.
A different generalization of boundary labeling considers sliding ports, i.e., labels are assigned disjoint intervals on the boundary of , and a site can be connected to any point in such an interval. In the 1sided model, Bekos et al. [5] gave an time algorithm that can minimize the total number of bends using leader (they did not require the leaders to lie strictly insider ). They posed an open question to determine the time complexity for the 3 and 4sided case. Benkert et al. [6] considered bend minimization with leaders. They gave an time algorithm for the 1sided model, and time algorithm for the opposite 2sided model. The ‘Handbook of Graph Drawing’ [17] lists a number of open problems related to the minimization of the total number of bends for different variants of boundary labeling.
The 1, 3 and 4sided models for the boundary labeling problem are always adjacent models, but a 2sided model can be either adjacent or opposite. Throughout the paper we will refer to the ‘opposite’ variant as an ‘opposite 2sided’ model.
Our Contributions:
We give an algorithm for the 1bend 2sided boundary labeling problem that minimizes the total leader length in time (if such a labeling exists). Ours is an adjacent model and uses leaders, and hence improves the time algorithm of Kindermann et al. [15]. Since the best known algorithm for the length minimization in the 1bend opposite 2sided model takes time [6], our result raises an intriguing question that whether the adjacent boundary labeling model can further be improved to reach (or, even break) the barrier.
We show that many variants of the boundary labeling problems can be related to outerstring graphs, where the minimization of total leader lengths or bends reduces to an optimization problem in those outerstring graphs. This idea leads us to the following results:

The first polynomialtime algorithm with a running time of for the 1bend 3sided and 4sided boundary labeling problem that minimize the total leader length. This settles the timecomplexity question posed by Kindermann et al. [15].

Polynomialtime algorithms for minimizing the total leader length or the total number of bends, even in the presence of obstacles. Our algorithms work for both  and leaders, as well as for all possible distributions of the ports to the boundary of , i.e., both adjacent and opposite models. The running time for the opposite 2sided model is for leaders and for leaders; these improve, respectively, the  and time algorithms of Fink and Suri [10]. This technique can also be applied to the sliding port model, which settles the timecomplexity question posed in [5, 17] related to the bend minimization.
2 Computing 1Bend 2Sided Boundary Labelings
In this section we give an time algorithm to find a solution to the 1bend 2sided boundary labeling problem. Throughout this section, we assume that the sites and ports are in general position, i.e., no axisaligned straight line passing through a site intersects a port or another site. Consequently, each leader must have exactly one bend. We thus omit the term ‘1bend’ in the rest of this section.
2.1 Technical Background
Let be the top, bottom, left and right sides of , respectively. An separating curve is an axisaligned monotone polygonal chain that starts at the bottomleft corner of and ends at the topright corner of . A 2sided boundary labeling solution is separated if there exists an separating curve such that the leaders incident to (resp., ) lie on or above (resp., below) the separating curve.
[Kindermann et al. [15]]If a 2sided boundary labeling problem has an affirmative solution with 1bend leaders, then there exists such an separated solution that minimizes the sum of all leader lengths.
Figure 2(a) illustrates an separated solution of a 2sided boundary labeling problem. An separated curve is shown in a lightgreen. Let be an instance of a 2sided boundary labeling problem. Without loss of generality assume that the ports are distributed along the sides and . Let (resp., ) be the set of ports along (resp., ). A leader is called inward if the angle formed at its bend point contains the topright corner of . Otherwise, we call the leader an outward leader. The leaders incident to and in Figure 2(a), are inward and outward leaders, respectively.
Assume that has an affirmative solution and let be a corresponding separating curve. Let be the polygonal region above bounded by and . Similarly, let be the polygonal region to the right of bounded by and . By (resp., ) we denote the separating curve that minimizes the area of (resp., ), e.g., see Figure 2(b). For a point , let and be its and coordinates, respectively. Given and , we define a sequence of rectangles as follows:

Each rectangle is a maximal rectangle between and .

The bottomleft corner of coincides with that of .

For , we first consider . Since is maximal, the top and right sides of must be determined by a pair of leaders, e.g., see in Figure 2(c). Denote these leaders by and , respectively. Let be the rightmost point on the top side of , and let be the topmost point on the right side of . We define to be the maximal empty rectangle with the bottomleft corner at and the sides bounded by and .
2.2 Algorithm
The idea of the algorithm is to employ a dynamic programming algorithm based on the idea of finding the optimal rectangle sequence . Note that for any rectangle , we can think of a subproblem that seeks a solution including the leaders and . The rectangle corresponding to this subproblem is determined by the vertical and horizontal segments of and , as illustrated in gray in Figure 3(a). It is straightforward to add a dummy rectangle with corresponding leaders and such that represents the original 2sided boundary labeling problem, e.g., see Figure 3(b).
Given , we try to find by checking all possible candidate rectangles. For convenience, we defer the details of finding all candidate rectangles, and focus on the computation of the solution cost (sum of leader length) assuming that we have found . Figure 3(c) illustrates such a scenario. Let be the region bounded by the lines determined by the vertical segments of and , horizontal segment of , and . Define symmetrically, e.g., see the top of Figure 4(i). Observe that is a 1sided boundary labeling problem with leaders and . In other words, since is an empty rectangle, all the ports between and must be connected to some site interior to . We define symmetrically. It is now straightforward to express the solution of in terms of the solutions of , and .
For any leader , we denote its length by . Let be the sum of the leader lengths in an optimal solution of (excluding the lengths of and ). Let and be the number of ports and sites interior to , excluding those that are incident to and . We now have the following recursive formula, where denotes the set of candidate rectangles.
Finding Candidate Rectangles:
Given a rectangle , we now describe how to find a set of candidate rectangles that must include . Recall that we can compute the bottomleft corner of from . Figures 4(a)–(d) illustrate the scenarios where and are inward. The point is marked with a cross. We claim that either the top or the right side of must contain a site (Lemma 2.2). We will use the following result of Benkert et al. [6] to prove Lemma 2.2.
[Benkert et al. [6]] For any solution to a 1bend 1sided boundary labeling problem that minimizes the total leader length (possibly with crossings), there exists a crossing free labeling with the total leader length at most the total leader length of .
Either the top or the right side of must contain a site.
Proof.
Suppose for a contradiction that neither the top nor the right side of contains a site. We now consider a few cases.
Case 1 (both and are inward): In this case the leaders and must intersect (see Figure 4(e)), which contradicts that the underlying solution is crossingfree.
Case 2 ( is inward and is outward): If is outward, then it must intersect (see Figure 4(f)). Therefore, the leader must be inward, as illustrated in Figure 4(g). Note that by our general position assumption, the ‘intervals’ determined by the vertical segments of and must overlap. Consequently, by swapping the site assignments, we can obtain a solution (possibly with crossings) with strictly smaller total leader length. Figure 4(i) illustrates such a scenario. By Lemma 4, we can replace this labeling of with a crossing free labeling that lies inside and does not increase the total leader length, e.g., see Figure 4(j). Note that the total leader length of the resulting solution would be strictly smaller, contradicting that the current solution is optimal.
Case 3 ( is outward and is inward): This case is symmetric to Case 2.
Case 4 (both and are outward): We can process this case in the same way as we did in Case 2. ∎
Recall that we know the bottomleft point of . We first assume that the right side of contains a site. For every site with and , we consider all possible empty rectangles with bottomleft corner , right side passing through and the top side determined by a horizontal line passing through a site above . Figures 4(k)–(l) illustrate the candidate rectangles for the bottom left point . We then assume that the top side of contains a site, and find the candidate rectangles symmetrically. We can now obtain an upper bound on the distinct candidate rectangles. The overall number of distinct candidate rectangles is .
Proof.
For a particular bottomleft corner , it may initially appear that there are possible candidate rectangles to explore. But we can prove an upper bound, as follows.
Let be the region dominated by ; i.e., for each point , the and coordinates of are at least as large as those of . Let be the set of sites in (ordered by increasing coordinates) such that no site in is dominated by any other site in (except possibly for ). We may assume without loss of generality (see Lemma 2.2) that the right side of contains a site. Since the proper interior of the rectangle is empty, for each , where , we only need to consider a set of heights that lie between and (or, between and when ). For every pair of sites , we have the property that neither nor dominates the other. Therefore, we have , , and thus a linear number of candidate rectangles for .
The number of possible intersections (i.e., bottomleft corners) among the horizontal and vertical lines passing through the ports and sites is . Therefore, the number of distinct candidate rectangles that may appear over the run of the algorithm is . ∎
Datastructures and Time Complexity:
If we use an dynamic programming table and compute each entry by checking candidate rectangles, then we need at least time. To improve the running time to , we preprocess the input. For every possible matching of a pair of ports (on the same side of ) to a pair of sites, we compute and store the solution to the corresponding 1sided boundary labeling problem. Since there are such 1sided problems, and each of them can be answered in time [6], this takes time. We first show how to reduce this preprocessing time to .
Consider a subproblem . Such a problem can easily be expressed by the ports and sites incident to and . Here we encode in a slightly different way. We use the parameters , where are the ports incident to and , is either or the coordinate of a site, and is the ‘type’ of . We will express as . In the following we describe the details of .
Note that to solve affirmatively, we need exactly as many free sites as the number of ports between and . Thus for any subproblem, if the number of free sites and free ports interior to do not match, then we can immediately return a negative answer. We assume that the points and ports are stored in an orthogonal range counting data structure (with time preprocessing) such that given an orthogonal rectangle, one can report the number of ports and points interior to the rectangle in time [7]. We only focus on those instances that have the same number of free sites and ports, and express them in the form .
Let be the sites that are incident to and , respectively. By the property of the optimal solution, we may assume that . We define as having type 0, 1, 2 or 3 depending on whether belongs to or not.
Type 1 (both are outside ): In this case the rectangle determined by the bend points of and must be empty (i.e., the gray region in Figure 5(a)). We set to be , and to be 1. During the algorithm execution, if is of Type 1, then we will seek a solution to .
Note that for any instance of the form , we can determine in time^{2}^{2}2It is straightforward to preprocess the ports and sites in time in a data structure to answer such queries in time. the point such that the rectangle determined by contains an equal number of free ports and sites. Note that the solution to the labeling problem inside will be equivalent to that of . We will precompute the solutions of so that can be answered in time by a table lookup. This general idea of answering a problem using applies also to the other types, i.e., Types 2,3 and 4.
Type 2 (both are inside ): In this case the rectangle determined by the bend point of and must be empty (Figures 5(b)–(c)). We thus set to be , and to be 2. Observe now that given , we can find both and in time^{2}^{2}footnotemark: 2 by counting the number of ports between and , and using .
Type 3 ( and ): In this case the rectangle determined by the bend point of and must be empty (Figure 5(d)). We thus set to be , and to be 3. Given , we can recover and using the range counting data structures^{2}^{2}footnotemark: 2. The same argument holds even when .
Type 4 ( and ): In this case the rectangle determined by the bend points of and must be empty (Figure 5(e)). We thus set to be , and to be 4. Given , we can recover using . Here we do not need to find since the solution must lie inside the rectangle determined by and .
The solution to the problems can be computed in time.
Proof.
First observe that there are possible choices for each of , and a constant number of choices for . Therefore, we have at most subproblems.
We can employ a dynamic programming to compute the solution to these problems. The idea is to select the bottommost free point and connect it to a port between and . This splits the problem into two subproblems, which can again be expressed in the form . Since the number of choices for is at most , we can compute an entry of the dynamic programming in time^{3}^{3}3We do not recompute the subproblems and perform a table lookup.. Since the number of entries is , the running time is bounded by .
We now show how to compute an entry using only a logarithmic number of queries, which would imply a running time of . Note that the problems of Types 1 and 4 can essentially be thought of as an 1sided problem, and we can precompute the solution of all such cases in time using Benkert et. al.’s [6] algorithm^{4}^{4}4For each pair of vertical lines passing through ports, we apply the algorithm to solve the 1bend 1sided problem using the topmost sites (if exists), where is the number of free ports between and .. We may thus assume without loss of generality that the problem is of Type 2 or 3.
Let be the rectangle determined by and the bend point of the leader of , i.e., the shaded rectangles in Figure 5. Note that no leader in the solution of would intersect . The union of the horizontal line of the leader of and the top side of defines a blocker, i.e., a segment that must not be intersected by any leader in the solution. Figure 6(a)–(b) illustrate a blocker in a thick line segment.
For any pair of ports , let be the stripe lying between the leaders incident to the ports and bounded by . We call a balanced stripe if and only if the number of free sites inside the stripe is equal to the number of free labels between . We call a port (between and ) a good port if is balanced (assuming that is connected to ), e.g., the ports and in Figures 6(a)–(b).
Let be the good ports ordered from left to right, and let , where , denote the 1sided boundary labeling problem determined by the leader of and the leader connecting to . By we denote the rightmost good port to the left of the blocker such that the has a feasible solution. We now consider two scenarios depending on whether exists or not.
Case 1 ( is the port immediately to the right of ): In this case we must connect to , and the region to the left of this leader must be empty, e.g., see the region with falling pattern in Figure 6(c). Suppose for a contradiction that is connected to some port in the optimal solution such that . Since is the bottommost site, must be balanced, and hence , a contradiction. Therefore, in this case we need only one table lookup to fill a dynamic programming table entry.
Case 2 (Otherwise): In this case there can be one or more good ports. We prove the following property in Section 3.

GoodPortSeparation: If has a feasible solution, then each of has a feasible solution. In addition, there exists an optimal solution of such that no leader crosses the vertical line through (except possibly the leaders of and ).
By the GoodPortSeparation property, the stripe represents a 1sided boundary labeling problem that can be solved using Benkert et al.’s algorithm [6]. Let and be the closest good ports to the left and right of , respectively. We then have to perform at most two table lookup, one for connecting to and the other for to . Note that if lies to the left of , then may not exist.
We now show how to test whether exists, and if so, then how to find and ; all in time. We rely on some preprocessing. For every site (which will play the role of ) and port , we precompute a list of good ports (sorted in increasing order of coordinates) to the right of the vertical line through , as illustrated in Figure 6(d). By the GoodPort Separation property, given , we can perform a binary search on the list of to decide whether exists. If exists, then another binary search for the coordinate of would locate and . ∎
Given a 1bend 2sided boundary labeling problem with sites and labels, one can find a labeling (if exists) that minimizes the total leader length in time.
Proof.
Every subproblem can be defined by a pair of leaders, and hence we can define an table to store the solutions to the subproblems. To compute an entry of the table , we look at a set of candidate rectangles with two nice properties. First, all these rectangles have the same bottomleft corner, and second, none of these rectangles can be a candidate rectangle for any other entry of . Therefore, the number of ‘candidate rectangle queries’ to fill all the entries of is bounded asymptotically by the number of distinct candidate rectangles, which is (by Lemma 2.2). Since we do not recompute solutions, and the table lookup takes time, the total running time is bounded by , which dominates the preprocessing time.
Observe that the complexity comes from considering all possible pairs of strings, whereas only options are relevant (by Lemma 2.2). Therefore, instead of a table, we can keep the relevant entries in a dynamic binary search tree, which increases the cost for solution lookup to , but limits the time for both the memory initialization and lookup queries to . Thus the total running time improves to . ∎
3 GoodPortSeparation Property
In this section, we prove the GoodPortSeparation property.
[GoodPortSeparation] If has a feasible solution, then each of has a feasible solution. In addition, there exists an optimal solution of such that no leader crosses the vertical line through (except possibly the leaders of and ).
Proof.
Suppose for a contradiction that is not feasible, where . We now construct a feasible solution as follows: We first construct a 1sided solution of (such a solution exists since the stripe is balanced [6]), e.g., see Figure 7(a). We know that has a feasible solution, where by definition, is connected to the bottommost point . We take such a solution of and remove the leader connecting and . We then connect to , and the stripe (including ) becomes balanced, e.g., see Figure 7(b). Consequently, we can construct a feasible labeling for , which contradicts that is not feasible.
We now show that there exists an optimal solution of such that no leader would cross the vertical line through (except possibly the leaders of and ). Assume that there exists an optimal solution , where some of the leaders intersect . Note that it would suffice to transform this solution into another solution that respects the separation by , and does not increase the sum of leader length, i.e., . We compute the transformation in two phases. In the first phase, we transform into some solution with that respects the separation, but possibly contains crossings among leaders. In the next phase we transform into some solution with , which is crossing free and respects the separation.
We first split into some regions as follows: Let be the blocker segment. Define to be the rectangle determined by , be the rectangle determined by , and be the rectangle bounded by the four lines determined by the horizontal segments of and , and the vertical lines through and . Figure 7(c) illustrates and . We now consider the following scenarios.
Case 1: First consider the case when there exists a site in whose leader does not intersect . Let be the port incident to this leader. Note that among the ports that lie to the right of , only the leaders incident to the ports between and may properly^{5}^{5}5The leader incident to intersects , but we do not consider that as a proper intersection. intersect (e.g., see Figure 7(d)). Since is balanced, if there is a set of such leaders intersecting , then there must be another set of leaders that are incident to the ports to the left of and intersect . Figure 7(d) illustrates these leaders in red and green, respectively. We now arbitrarily compute pairs, taking one leader from each set, and swap their sites. Such a swap may create edge crossings (e.g., see Figures 8(a)–(b)). However, they do not increase the total leader length, as illustrated in Figures 8(c)–(f). This yields the solution that respects the separation by . The solution to the left and to the right of now can independently be modified to remove the crossing by using a result of Benkert et al. [6, Lemma 1].
Case 2: Consider now the case when all the sites of intersect . Let be the number of sites interior to , and let be the set of leaders incident to these sites (the green leaders in Figure 9(a)). Recall that has a feasible solution. Let be the ports from left to right in that are connected to the sites in in an optimal solution of , e.g., see Figure 9(b). Let be the port incident to .
Since the leaders in are crossing , any other leader crossing and incident to a port to the right of , must lie above the line determined by the blocker. Assume that there are such leaders and define to be the set that consists of these leaders (i.e., the red leaders in Figure 9(a)). Consequently, we must have another set of leaders that are incident to the ports lying to the left of and intersecting (i.e., the blue leader in Figure 9(a)). Denote these set of leaders by . Since the leaders in cover all the points in , each leader in must lie above the line determined by the blocker.
We now construct pairs of leaders, taking one leader from and one from , and for each pair, we swap their sites. Similar to Case 1, these swaps do not increase the total leader length, but may introduce crossings among the leaders (Figure 9(c)). However, at the end of all these swaps, we only have and a set of leaders crossing .
Let be the vertical line through . Assume that there are leaders that are incident to the ports in and cross . Recall that the 1sided problem determined by and the leader connecting has a feasible solution. Therefore, the rectangle bounded by , and the blocker is balanced (e.g., see Figure 9(d)). Thus there must be exactly leaders that connect ports from the left of and enter (e.g., the orange leaders in Figure 9(d)). We can swap the sites of these two sets of leaders (as we did for ) without increasing the total leader length (e.g., see Figure 9(e)). It is now straightforward to compute a planar solution inside using Benkert et al.’s algorithm [6, Lemma 1].
Note that the newly formed , i.e., the leaders that are incident the ports on the right halfplane of and cross , now lie entirely in . Therefore, we can swap the sites of the sets and , and then remove the crossings on the left and right halfplanes of independently using Benkert et al.’s algorithm [6, Lemma 1].
Case 3: The remaining case is when is empty, which is straightforward to process in the way we handled Case 1. ∎
4 Relating Boundary Labeling to Outerstring Graphs
In this section, we reduce the boundary labeling problem to the independent set problem on a class of weighted geometric intersection graphs in the plane called outerstring graphs. We show that if one can discretize a boundary labeling problem such that the number of candidate leaders is a polynomial in , then our approach will yield a polynomialtime algorithm for the problem.
An outerstring graph is an intersection graph of a set of curves in the Euclidean plane that lie inside a polygon such that one of the endpoints of each curve is attached to the boundary of the polygon. Keil et al. [14] gave an time algorithm for the maximumweighted independent set problem on outerstring graphs. The algorithm requires an outerstring graph as an input, where each curve is given as a polygonal line (i.e., a chain of straight line segments) and is the number of segments in the representation. We show that by discretizing the boundary labeling problem and assigning an appropriate weight to each candidate leader, one can reduce the boundary labeling problem to the maximumweighted independent set problem on outerstring graphs. As an example, here we show the reduction for the boundary labeling problem using leaders in the presence of obstacles.
Boundary Labeling with Orthogonal Obstacles:
Fink and Suri [10] gave and time algorithms for the opposite 2sided boundary labeling with and leaders, respectively. Our approach will yield and time algorithms for  and leaders, respectively, irrespective of the labeling model (opposite, adjacent, or for any port distribution on the boundary). For the opposite 2sided case, the running time reduces to and (for  and leaders, respectively). This will settle the time complexity question of 1bend 3 and 4sided boundary labeling [15]. In the rest of this section, we relax the general position assumption and denote to be the total number of sites and obstacle vertices.
First consider the case of leaders. Let be an instance of the boundary labeling. Given a site and a port, there is at most one way of connecting them. Let denote the set of all possible leaders that do not intersect any obstacle. Then . It is straightforward to compute in time. Observe that each leader can be viewed as an outerstring, and let be the corresponding outerstring. Let be the length of the leader , and define and . Let be a number such that . For each leader , we assign a weight to , where . The following lemma and Keil et al.’s [14] algorithm lead us to the results for leaders (Theorem 4). has a feasible solution with total leader length if and only if the corresponding outerstring graph has a feasible solution with total weight .
Proof.
A feasible solution of with total leader length gives a feasible solution for with total weight
We now assume that has a feasible solution with total weight , and show that the corresponding leaders yields a feasible solution of of total leader length . Since is an independent set, the leaders in are crossingfree, as well as no site or port is incident to more than one leader. It now suffices to show that every site is connected to a string, i.e., and the total leader length is . Observe that . If , then the total leader length is at most , and has weight at most , which contradicts that . Therefore, , and we have
Since , we have . ∎
The boundary labeling problem can be solved in time using leaders, for both adjacent and opposite sided models, even in the presence of obstacles (where is the total number of sites and vertices of the obstacles).
Consider now the case for leaders. For opposite 2sided case, Fink and Suri [10] showed that one can discretize the problem such that if there exists a feasible solution, then there is one where the coordinate of the middle segment of every leader lies in the set of all coordinates of the sites and obstacle vertices. Therefore, we have potential leaders for each portsite pair, and thus leaders in total. Hence applying Keil et al.’s [14] algorithm gives a running time of .
The discretization of [10] does not apply to the 3 and 4sided case. However, consider a grid determined by the axisaligned lines through the ports, sites and obstacle vertices. For each pair of consecutive parallel lines of , place a set of parallel lines in between. Let the resulting grid be . If there is a feasible solution to the boundary labeling problem, then for any pair of consecutive parallel vertical lines (similarly for horizontal) of , we can have at most middle vertical segments of the leaders. We thus can distribute them by moving horizontally to the lines of (e.g., see [10]), which does not change the total leader length. By construction, there is no site, port or obstacle vertex between and . Hence such a modification can be performed without introducing any crossing. Since is an grid and since we have potential leaders for each portsite pair, the number of candidate leaders is . Hence applying Keil et al.’s [14] algorithm gives a running time of .
The adjacent boundary labeling problem can be solved in time using leaders, even in the presence of obstacles (where is the total number of sites and vertices of the obstacles). For opposite 2sided models, the running time reduces to .
Sliding Port and Bend Minimization:
The outerstringgraph approach can also be applied to the sliding port model, where each label is assigned a distinct interval on the boundary of and a site can be connected to any point of an interval. The goal here is to minimize the total leader length or the number of bends. We only need to discretize the problem such that the number of strings that we need to consider is a polynomial in . Define to be a grid determined by the axisaligned lines through sites, interval boundaries and obstacle vertices. Construct from by introducing for every pair of consecutive parallel lines of , a set of parallel lines in between.
The grid can be used to discretize the problem, as follows. The segments incident to the sites are already on . Consider now a vertical (similarly for horizontal) segment that is incident to an interval , but not incident to any site. Let and be a pair of consecutive horizontal lines of such that lies between them. There can be at most horizontal lines between , which we can distribute to the lines of by moving vertically (e.g., see [10]). Since there cannot be any site, interval boundary or obstacle vertex between , such a modification neither introduce crossings nor increase the number of total bends. By the construction of , the boundary of between lies in the interval . Hence will still be incident to . Finally, the middle segments of the leaders can be processed in the same way as we did for Theorem 4. It is straightforward to observe that the number of potential strings is a polynomial in . We can now assign certain weights to these strings such that the maximumweight independent set of the corresponding outerstring graph yields a minimumbend solution for the boundary labeling problem.
We first consider the case of leaders. Let be an instance of this problem. Consider the set of outerstrings as before. For each outerstring , we assign the weight , where
(1) 
This forms our instance of an outerstring graph on which we solve the maximumweighted independent set problem by running Keil et al.’s algorithm [14]. Let be an instance of the boundary labeling problem with leaders. Then has a feasible solution with bends if and only if the instance has a feasible solution with total weight at least .
Proof.
Let be a feasible solution of . Clearly, the strings corresponding to the leader of is a feasible solution for . Let be the total number of bends in . Then the weight of is
Assume now that has a feasible solution with weight at least . Let be the corresponding set of leaders in . Since is an independent set, a port or site can be incident to at most one leader of . If a site is not connected to any port in , then at most sites are incident to a leader. Since the maximum weight of a leader can be at most , the weight of is at most , which is a contradiction since the weight of is at least (because ). Therefore, .
It now remains to show that the weight of is at most . Suppose for a contradiction that has at least leaders. Therefore, the weight of is at most , which is a contradiction that the weight of is at least . ∎
Now, we consider the case of leaders. Let be an instance of this problem. Consider the set of outerstrings as before. For each outerstring , we assign the weight as follows:
(2) 
Here .
Let be an instance of the boundary labeling problem with leaders. Then has a feasible solution with bends if and only if the instance has a feasible solution with total weight at least .
Proof.
Let be a feasible solution of . Clearly, the strings corresponding to the leader of is a feasible solution for . Let be the total number of bends in , and let and be the number of strings with 1bend and 2bends, respectively. Therefore, , and the weight of is
Assume now that has a feasible solution with weight at least . Let be the corresponding set of leaders in . Since is an independent set, a port or site can be incident to at most one leader of . If a site is not connected to any port in , then at most sites are incident to a leader. Since the maximum weight of a leader can be at most , the weight of is at most , which is a contradiction since the weight of is at least (because ). Therefore, .
It now remains to show that the leaders of has at most bends. Suppose for a contradiction that has at least leaders and leaders such that . Therefore, the weight of is at most . Since , the weight of is strictly less than , which is a contradiction. ∎
By Lemmas 1 and 4, we have the following theorem (which settles two open questions of [17, Table 23.1]). A boundary labeling that minimizes the total number of bends can be computed (if exists) in polynomial time for both adjacent and opposite models (with sliding ports, and leaders), even in the presence of obstacles.
5 Conclusion
The most natural directions for future research is to improve the time complexity of our algorithm for the 1bend adjacent 2sided model. A number of intriguing questions follow: Can we find a nontrivial lower bound on the timecomplexity? Is the problem 3sum hard or, as hard as ‘sorting ’? Can we check the feasibility in nearlinear time? It would also be interesting to find fast approximation algorithms for boundary labeling problems.
References
 [1] Alexander Wolff and Tycho Strijk. The maplabeling bibliography. http://i11www.ira.uka.de/maplabeling/bibliography/, 1996. Online; accessed 10 February, 2018.
 [2] Lukas Barth, Benjamin Niedermann, Martin Nöllenburg, and Darren Strash. Temporal map labeling: A new unified framework with experiments. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), pages 23:1–23:10. ACM, 2016.
 [3] Michael A. Bekos, Sabine Cornelsen, Martin Fink, SeokHee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, and Antonios Symvonis. Manytoone boundary labeling with backbones. J. Graph Algorithms Appl., 19(3):779–816, 2015.
 [4] Michael A. Bekos, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis. Boundary labeling with octilinear leaders. Algorithmica, 57(3):436–461, 2010.
 [5] Michael A. Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Comput. Geom., 36(3):215–236, 2007.
 [6] Marc Benkert, Herman J. Haverkort, Moritz Kroll, and Martin Nöllenburg. Algorithms for multicriteria boundary labeling. J. Graph Algorithms Appl., 13(3):289–317, 2009.
 [7] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, Berlin Heidelberg, 2008.
 [8] Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Bernard M. E. Moret, and Binhai Zhu. Map labeling and its generalizations. In Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 148–157, 1997.
 [9] William S. Evans, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Debajyoti Mondal, Rahnuma Islam Nishat, and Kevin Verbeek. Table cartogram. Comput. Geom., 68:174–185, 2018.
 [10] Martin Fink and Subhash Suri. Boundary labeling with obstacles. In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), pages 86–92, 2016.
 [11] Michael Formann and Frank Wagner. A packing problem with applications to lettering of maps. In Proceedings of the Seventh Annual Symposium on Computational Geometry (SoCG), pages 281–288. ACM, 1991.
 [12] Herbert Freeman. An expert system for the automatic placement of names on a geographic map. Inf. Sci., 45(3):367–378, 1988.
 [13] Stephen A. Hirsch. An algorithm for automatic name placement around point data. The American Cartographer, 9(1):5–17, 1982.
 [14] J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle. An algorithm for the maximum weight independent set problem on outerstring graphs. Comput. Geom., 60:19–25, 2017.
 [15] Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, and Alexander Wolff. Multisided boundary labeling. Algorithmica, 76(1):225–258, 2016.
 [16] Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski. Dynamic onesided boundary labeling. In 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS), pages 310–319, 2010.
 [17] Alexander Wolff. Graph drawing and cartography. In Roberto Tamassia, editor, Handbook of graph drawing and visualization, chapter 23, pages 697–736. CRC Press, 2014.
 [18] Steven Zoraster. The solution of large 01 integer programming problems encountered in automated cartography. Operations Research, 38(5):752–759, 1990.
 [19] Steven Zoraster. Practical results using simulated annealing for point feature label placement. Cartography and GIS, 24(4):228–238, 1997.
Comments
There are no comments yet.