Edge bundling reduces the visual clutter in a drawing of a graph by uniting the edges into bundles. We propose a method of edge bundling drawing each edge of a bundle separately as in metro-maps and call our method ordered bundles. To produce aesthetically looking edge routes it minimizes a cost function on the edges. The cost function depends on the ink, required to draw the edges, the edge lengths, widths and separations. The cost also penalizes for too many edges passing through narrow channels by using the constrained Delaunay triangulation. The method avoids unnecessary edge-node and edge-edge crossings. To draw edges with the minimal number of crossings and separately within the same bundle we develop an efficient algorithm solving a variant of the metro-line crossing minimization problem. In general, the method creates clear and smooth edge routes giving an overview of the global graph structure, while still drawing each edge separately and thus enabling local analysis.
Asquith et al. @cite_12 defined the so-called MLCM-FixedSE problem, in which it is specified whether a path terminates at the top or bottom of its terminal node. For a graph @math and a set of paths @math they give the algorithm with @math time complexity. A closely related problem called MLCM-T1, in which all paths connect degree- @math terminal nodes in @math , was considered by Argyriou et al. @cite_5 . Their algorithm computes an optimal ordering of paths and has a running time of @math . Recently, N "o llenburg @cite_16 presented an @math -time algorithm for these variants of the MLCM problem. Our algorithm can be used to solve both the MLCM-FixedSE and MLCM-T1 problems with complexity @math . To the best of our knowledge, this is the fastest solution to date of these variants of MLCM.
@cite_5 @cite_16 @cite_12
2114857285 1765507333 2952103668 1970202342
We consider the problem of drawing a set of simple paths along the edges of an embedded underlying graph G = (V,E), so that the total number of crossings among pairs of paths is minimized. This problem arises when drawing metro maps, where the embedding of G depicts the structure of the underlying network, the nodes of G correspond to train stations, an edge connecting two nodes implies that there exists a railway line which connects them, whereas the paths illustrate the lines connecting terminal stations. We call this the metro-line crossing minimization problem (MLCM). In contrast to the problem of drawing the underlying graph nicely, MLCM has received fewer attention. It was recently introduced by Benkert et. al in [4]. In this paper, as a first step towards solving MLCM in arbitrary graphs, we study path and tree networks.We examine several variations of the problem for which we develop algorithms for obtaining optimal solutions. The metro-line crossing minimization (MLCM) problem was recently introduced as a response to the problem of drawing metro maps or public transportation networks, in general. According to this problem, we are given a planar, embedded graph G = (V ,E ) and a set L of simple paths on G , called lines . The main task is to place the lines on G , so that the number of crossings among pairs of lines is minimized. Our main contribution is two polynomial time algorithms. The first solves the general case of the MLCM problem, where the lines that traverse a particular vertex of G are allowed to use any side of it to either "enter" or "exit", assuming that the endpoints of the lines are located at vertices of degree one. The second one solves more efficiently the restricted case, where only the left and the right side of each vertex can be used. To the best of our knowledge, this is the first time where the general case of the MLCM problem is solved. Previous work was devoted to the restricted case of the MLCM problem under the additional assumption that the endpoints of the lines are either the topmost or the bottommost in their corresponding vertices, i.e., they are either on top or below the lines that pass through the vertex. Even for this case, we improve a known result of from O (|E |5 2|L |3) to O (|V |(|E | + |L |)). The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in @math time, where @math is the number of vertices in the input graph @math . Peleg and Rubinovich (FOCS'99) showed a lower bound of @math for this problem, where @math is the hop-diameter of @math . Whether or not this problem can be solved in @math time when @math is relatively small is a major notorious open question. Despite intensive research LP13,N14,HKN15,EN16,BKKL16 that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the affirmative. We devise an algorithm that requires @math time, for @math , and @math time, for larger @math . This running time is sublinear in @math in almost the entire range of parameters, specifically, for @math . For the all-pairs shortest paths problem, our algorithm requires @math time, regardless of the value of @math . We also devise the first algorithm with non-trivial complexity guarantees for computing exact shortest paths in the multipass semi-streaming model of computation. From the technical viewpoint, our algorithm computes a hopset @math of a skeleton graph @math of @math without first computing @math itself. We then conduct a Bellman-Ford exploration in @math , while computing the required edges of @math on the fly. As a result, our algorithm computes exactly those edges of @math that it really needs, rather than computing approximately the entire @math . Consider a bipartite graph G = (O, D, E) where O and D are origin and destination node sets respectively (O = D = n), and E is a set of edges (i, j), i ∈ O and j ∈ D(E= m). Suppose we draw the origin nodes and the destination nodes arranged in two columns and the edges as straight line segments between origins and destinations. A noncrossing matching is a subset of edges M ⊑ E such that no two edges of M intersect (including intersections at nodes). The Maximum Non Crossing Matching (MNCM) is the problem of finding the noncrossing matching of maximum cardinality. Let p denote the cardinality of the MNCM. Problems arising in several fields can be modelled as MNCM: for example the 3-Side Switch Box in VLSI design has been presented in [2] where an O(n 2) time algorithm is proposed. The problem can be reduced to the one of finding the longest increasing subsequence in a permutation of size m [1]. An algorithm for this problem has been proposed by Fredman and slightly improved by Widmayer and Wong[7]; in our case the algorithm complexity is O(m + (m - p) log (p). In this paper some labeling algorithms for the MNCM, which work directly on the bipartite graph, will be proposed. The overall complexity is improved to O(m log log n) or to O(m + minnp, (m - p) log p). Finally the weighted case is considered.