We study an important practical aspect of the route planning problem in real-world road networks -- maneuvers. Informally, maneuvers represent various irregularities of the road network graph such as turn-prohibitions, traffic light delays, round-abouts, forbidden passages and so on. We propose a generalized model which can handle arbitrarily complex (and even negative) maneuvers, and outline how to enhance Dijkstra's algorithm in order to solve route planning queries in this model without prior adjustments of the underlying road network graph.
The first, and seemingly the simplest, solution is commonly used as it makes a road network graph maneuver-free and so there is no need to adjust the queries in any way. Unfortunately, it can significantly increase the size of the graph @cite_12 ; for instance, replacing a single turn-prohibition can add up to eight new vertices in place of one original @cite_9 . A solution like this one thus conflicts with the aforementioned (graph-size) objectives. Another approach @cite_10 uses so-called dual graph representation instead of the original one, where allowed turns are modeled by dual edges.
@cite_9 @cite_10 @cite_12
1991924366 2091662631 1482690689 2155044259 2239163339 2067935583 176560628 137863291 2963014036 2014447809 2092349993 2534944111 1999757901 2161779091 2098322943 2070232376 2008562682 2004951603 2021989224 2794478167
In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogota’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine. The purpose of this paper is to describe the dual graph technique developed by the authors to represent transport networks. The method is intended to simplify the coding of complex transport networks to a considerable degree, particularly when there are turning restrictions, or when multiple transfers between modes or transit lines must be taken into account. A first section presents the traditional form in which transport networks are analytically represented, and describes the main problems that are confronted. In particular, the difficulty to represent prohibited turns is shown to be a major problem; when such a restriction is introduced, the representation of the network becomes increasingly complex and intractable, requiring a large number of fictitious links and nodes. A second section describes the dual graph technique in general terms, and shows how the network code remains simple, even if prohibited turns are introduced, completely avoiding fictitious links and the possibility of errors. A third section describes the way in which dual networks are constructed in formal terms. It is shown that the process of constructing the dual graph can be automated easily, becoming completely transparent to the model user. In a fourth section the method is extended to represent transit routes or, in general, multiple operators and modes. This is achieved by introducing further dimension to the dual network (multidimensional networks); the dual of very complex transit networks can also be automated, avoiding the need for fictitious nodes and links to represent transfer points. A final section draws the main conclusions and points out that dual graphs can be very useful for detailed traffic models. Brief references are made to other known methods to represent turn restrictions. In this paper a model that handles costs of turns in route planning is defined, investigated and discussed. Costs are traditionally attached to edges in a graph. For some important route planning problems other costs can be identified, namely costs that appear when leaving one edge and entering the next. Examples are turn restrictions, the turning angle, or the simple necessity to turn. Such costs cannot be stored as attributes of nodes or edges in the graph, and they cannot be handled correctly by shortest path algorithms without modifications. Turn costs can be represented by a pseudo-dual graph in a way that shortest path algorithms run without modifications. Although the idea is not new, it has not found much interest in the literature. The pseudo-dual graph is defined here in a new way, it is systematically investigated, and some practical applications are shown. Concentrating strictly on topology, it turns out that the pseudo-dual graph is conceptually cleaner and more efficient in route planning than alternative, currently used ways to deal with turn costs. The discussed applications are from the field of pedestrian navigation, which gave rise to this research. We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective. There is a large number of effective methodologies and algorithms for the creation of aesthetically pleasing graph drawings in two dimensions. However, representing graphs in three dimensions offers various benefits. The extra dimension gives greater flexibility for placing the vertices and edges of a graph and crossings can be always avoided. On the other hand new challenges arise: current output media have a two-dimensional nature and can only provide a limited resolution and display area. Thus, the resulting drawings become complex and difficult to survey. These disadvantages can be weakened by the use of navigational operations such as rotation, shifting and zooming. These operations enable an effective use of screen space and allow users to resolve ambiguities in large graphs while maintaining their overall mental map. The possibility of changing the viewpoint in 3D will also diminish the relevance of edge crossing in the (two-dimensional) screen representation of the graph. In practical military or first responder deployment scenarios, information flows need to adhere to specified policies regardless of the physical connectivity of nodes. Nodes in such networks are associated with various levels in a command-and-control hierarchy, and therefore typically form a logical hierarchical tree network that is used to route both command and data traffic. Associated with this logical hierarchical network is a communication network that represents the connectivity of these nodes in the deployed scenario. Such composite networks introduce constraints that can result in information flows having to traverse much longer paths in the underlying communication network. In this paper, we look at the problem of adding edges to a logical hierarchical network (or any other social network) so as to minimize the number of hops required to route data traffic in the underlying communication network from a node to other specified nodes. The edges added are a subset of all possible edges in the complementary logical hierarchical graph and have to satisfy specified hierarchical constraints. First, we consider the general problem of minimizing the eccentricity of a source node 's' (where eccentricity of 's' is the maximum of the shortest paths from 's' to all other nodes) in a metric graph on adding upto 'B' unequal cost metric edges from the set of all edges in the complementary graph. We develop an efficient constant factor approximation algorithm for this case that outperforms existing constant factor algorithms for eccentricity minimization. Here the added edge metric cost as well as the graph edge metric cost correspond to the number of hops in the shortest path required to route traffic in the actual deployed topology (i.e., underlying communication network). Next, we consider the case where the set of possible added edges is a specified subset of the edges in the complementary graph and the set of destinations is a subset of the graph nodes. For this case, we develop heuristic algorithms based on the previous eccentricity minimizing algorithm that show good performance. We validate our algorithms using two realistic military deployment scenarios. We find that adding even a low number of hierarchically constrained edges (of the order of 10) can cause a significant decrease (around 50 ) in the eccentricity of a node in the logical hierarchical network and thus can reduce the number of hops required for data traffic traversal. We address the problem of graph rewriting and narrowing as the underlying operational semantics of rule-based programming languages. We propose new optimal graph rewriting and narrowing strategies in the setting of orthogonal constructor-based graph rewriting systems. For this purpose, we first characterize a subset of graphs, called admissible graphs. A graph is admissible if none of its defined operations belongs to a cycle. We then prove the confluence, as well as the confluence modulo bisimilarity (unraveling), of the admissible graph rewriting relation. Afterwards, we define a sequential graph rewriting strategy by using Antoy’s definitional trees. We show that the resulting strategy computes only needed redexes and develops optimal derivations w.r.t. the number of steps. Finally, we tackle the graph narrowing relation over admissible graphs and propose a sequential narrowing strategy which computes independent solutions and develops shorter derivations than most general graph narrowing. Many real-world domains can be represented as large node-link graphs: backbone Internet routers connect with 70,000 other hosts, mid-sized Web servers handle between 20,000 and 200,000 hyperlinked documents, and dictionaries contain millions of words defined in terms of each other. Computational manipulation of such large graphs is common, but previous tools for graph visualization have been limited to datasets of a few thousand nodes. Visual depictions of graphs and networks are external representations that exploit human visual processing to reduce the cognitive load of many tasks that require understanding of global or local structure. We assert that the two key advantages of computer-based systems for information visualization over traditional paper-based visual exposition are interactivity and scalability. We also argue that designing visualization software by taking the characteristics of a target user's task domain into account leads to systems that are more effective and scale to larger datasets than previous work. This thesis contains a detailed analysis of three specialized systems for the interactive exploration of large graphs, relating the intended tasks to the spatial layout and visual encoding choices. We present two novel algorithms for specialized layout and drawing that use quite different visual metaphors. The H3 system for visualizing the hyperlink structures of web sites scales to datasets of over 100,000 nodes by using a carefully chosen spanning tree as the layout backbone, 3D hyperbolic geometry for a Focus+Context view, and provides a fluid interactive experience through guaranteed frame rate drawing. The Constellation system features a highly specialized 2D layout intended to spatially encode domain-specific information for computational linguists checking the plausibility of a large semantic network created from dictionaries. The Planet Multicast system for displaying the tunnel topology of the Internet's multicast backbone provides a literal 3D geographic layout of arcs on a globe to help MBone maintainers find misconfigured long-distance tunnels. Each of these three systems provides a very different view of the graph structure, and we evaluate their efficacy for the intended task. We generalize these findings in our analysis of the importance of interactivity and specialization for graph visualization systems that are effective and scalable. We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc. We show that the Ranking algorithm by (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 The main question addressed in this article is the following: If t edges are removed from a (t + 1) edge-connected graph G having diameter D, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D. The bulk of the proof consists of showing that, if t edges are added to an n-vertex path Pn, then the diameter of the resulting graph is at least (n (t + 1)) - 1. Using a similar proof, we also show that if t edges are added to an n-vertex cycle Cn, then the least possible diameter of the resulting graph is (for large n) essentially n (t + 2) when t is even and n (t + 1) when t is odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the corresponding vertex deletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time-delay or signal degradation is directly related to the diameter of the network. Chapter 36 Decomposing Graphs into Regions of Small Diameter* Nathan Linialt Michael .lss A decomposition of a graph G = (V, E) is a partition of the vertex set into subsets (called lhks). The diameter of a decomposition is the least. d such that any two vertices belonging to the same connected component of a block are at distance < d. In this paper we prove (nearly best possible) statements of the form: .4ny n–vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [AGLP1 it was shown that every graph has a decomposition into at most s(n) blocks of diameter at most s(n) for s(n) = o( loglog d h n). usinga,technique of Awerbuch [A] and Awerbuch and Peleg [AP], we improve this result by showing that every graph has a decomposition of diameter ()(log n) into O(log n) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in time 0(log2 n). The construction can be parametrized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible for two families of graphs the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner’s lemma for the first class and Tucker’s lemma for the second. *This work was supported in part by NSF contracts DMS87-03541 and CCR-8911388 tDepartment of Computer Science, Hebrew University, Jerusalem, Israel. + ‘Department of Computer Science and Engineering, Mail Code C-014, University of California, San Diego, La Jolla, CA 92093-0114. We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: • We present a poly log n round deterministic algorithm for (2Δ−1)·(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ − 1) · poly log Δ-edge-coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. • We show that sinkless orientation---i.e., orienting edges such that each node has at least one out-going edge---on Δ-regular graphs can be solved in O(logΔ log n) rounds randomized and in O(logΔ n) rounds deterministically. These prove the corresponding lower bounds by [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of for Δ-coloring Δ-regular trees. • We present a randomized O(log4 n) round algorithm for orienting a-arboricity graphs with maximum out-degree a(1 + e). This can be also turned into a decomposition into a(1 + e) forests when a = Ω(log n) and into a(1 + e) pseduo-forests when a = o(log n). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin. We consider a well-known distributed colouring game played on a simple connected graph: initially, each vertex is coloured black or white; at each round, each vertex simultaneously recolours itself by the colour of the simple (strong) majority of its neighbours. A set of vertices M is said to be a dynamo, if starting the game with only the vertices of M coloured black, the computation eventually reaches an all-black configuration.The importance of this game follows from the fact that it models the spread of faults in point-to-point systems with majority-based voting; in particular, dynamos correspond to those sets of initial failures which will lead the entire system to fail. Investigations on dynamos have been extensive but restricted to establishing tight bounds on the size (i.e., how small a dynamic monopoly might be).In this paper we start to study dynamos systematically with respect to both the size and the time (i.e., how many rounds are needed to reach all-black configuration) in various models and topologies.We derive tight tradeoffs between the size and the time for a number of regular graphs, including rings, complete d-ary trees, tori, wrapped butterflies, cube connected cycles and hypercubes. In addition, we determine optimal size bounds of irreversible dynamos for butterflies and shuffle-exchange using simple majority and for DeBruijn using strong majority rules. Finally, we make some observations concerning irreversible versus reversible monotone models and slow complete computations from minimal dynamos. We present a simple generation procedure which turns out to be an effective source of very hard cases for graph 3-colorability. The graphs distributed according to this generation procedure are much denser in very hard cases than previously reported for the same problem size. The coloring cost for these instances is also orders of magnitude bigger. This ability is issued from the fact that the procedure favors-inside the class of graphs with given connectivity and free of 4-cliques-the generation of graphs with relatively few paths of length three (that we call 3-paths). There is a critical value of the ratio between the number of 3-paths and the number of edges, independent of the number of nodes, which separates the graphs having the same connectivity in two regions: one contains almost all graphs free of 4-cliques while the other contains almost no such graphs. The generated very hard cases are near this phase transition, and have a regular structure, witnessed by the low variance in node degrees, as opposite to the random graphs. This regularity in the graph structure seems to confuse the coloring algorithm by inducing an uniform search space, with no clue for the search. We prove that any graph excluding Kr as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O(r Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O(r2 Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O(r) and strong-diameter partitions with padding parameter O(r2) for Kr-free graphs, O(k) for treewidth-k graphs, and O(log g) for graphs with genus g. Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [Bui and Jones, Proc. of the 6th SIAM Conference on Parallel Processing for Scientific Computing, 1993, 445--452; Hendrickson and Leland, A Multilevel Algorithm for Partitioning Graphs, Tech. report SAND 93-1301, Sandia National Laboratories, Albuquerque, NM, 1993]. From the early work it was clear that multilevel techniques held great promise; however, it was not known if they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme produces partitions that are consistently better than those produced by spectral partitioning schemes in substantially smaller time. Also, when our scheme is used to compute fill-reducing orderings for sparse matrices, it produces orderings that have substantially smaller fill than the widely used multiple minimum degree algorithm. 2-Edge connectivity is an important fault tolerance property of a network because it maintains network communication despite the deletion of a single arbitrary edge. Planar spanning subgraphs have been shown to play a significant role for achieving local decentralized routing in wireless networks. Existing algorithmic constructions of spanning planar subgraphs of unit disk graphs (UDGs) such as Minimum Spanning Tree, Gabriel Graph, Nearest Neighborhood Graph, etc. do not always ensure connectivity of the resulting graph under single edge deletion. Furthermore, adding edges to the network so as to improve its edge connectivity not only may create edge crossings (at points which are not vertices) but it may also require edges of unbounded length. Thus we are faced with the problem of constructing 2-edge connected geometric planar spanning graphs by adding edges of bounded length without creating edge crossings (at points which are not vertices). To overcome this difficulty, in this paper we address the problem of augmenting the edge set (i.e., adding new edges) of planar geometric graphs with straight line edges of bounded length so that the resulting graph is planar and 2-edge connected. We provide bounds on the number of newly added straight-line edges, prove that such edges can be of length at most 3 times the max length of an edge of the original graph, and also show that the factor 3 is optimal. It is shown to be NP-Complete to augment a geometric planar graph to a 2-edge connected geometric planar graph with the minimum number of new edges of a given bounded length. We also provide a constant time algorithm that works in location-aware settings to augment a planar graph into a 2-edge connected planar graph with straight-line edges of length bounded by 3 times the longest edge of the original graph. It turns out that knowledge of vertex coordinates is crucial to our construction and in fact we prove that this problem cannot be solved locally if the vertices do not know their coordinates. Moreover, we provide a family of k-connected UDGs which does not have 2-edge connected spanning planar subgraphs, for any . In this paper, we present and study a class of graph partitioning algorithms that reduces the size of the graph by collapsing vertices and edges, we find ak-way partitioning of the smaller graph, and then we uncoarsen and refine it to construct ak-way partitioning for the original graph. These algorithms compute ak-way partitioning of a graphG= (V,E) inO(|E|) time, which is faster by a factor ofO(logk) than previously proposed multilevel recursive bisection algorithms. A key contribution of our work is in finding a high-quality and computationally inexpensive refinement algorithm that can improve upon an initialk-way partitioning. We also study the effectiveness of the overall scheme for a variety of coarsening schemes. We present experimental results on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that this new scheme produces partitions that are of comparable or better quality than those produced by the multilevel bisection algorithm and requires substantially smaller time. Graphs containing up to 450,000 vertices and 3,300,000 edges can be partitioned in 256 domains in less than 40 s on a workstation such as SGI's Challenge. Compared with the widely used multilevel spectral bisection algorithm, our new algorithm is usually two orders of magnitude faster and produces partitions with substantially smaller edge-cut. Let fd (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n0 (D) vertices, f2(G) = n - D - 1 and f3(G) ≥ n - O(D3). For d ≥ 4, fd (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of fd (G) over all connected graphs on n vertices is n-⌊d-2 ⌋ - O(1). As a byproduct, we show that for the n-cycle Cn, fd (Cn) = n-(2⌊d-2 ⌋ - 1) - O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000 1991 Mathematics Subject classification: 05C12. In the subgraph-freeness problem, we are given a constant-sized graph H, and wish to de- termine whether the network graph contains H as a subgraph or not. Until now, the only lower bounds on subgraph-freeness known for the CONGEST model were for cycles of length greater than 3; here we extend and generalize the cycle lower bound, and obtain polynomial lower bounds for subgraph-freeness in the CONGEST model for two classes of subgraphs. The first class contains any graph obtained by starting from a 2-connected graph H for which we already know a lower bound, and replacing the vertices of H by arbitrary connected graphs. We show that the lower bound on H carries over to the new graph. The second class is constructed by starting from a cycle Ck of length k ≥ 4, and constructing a graph H from Ck by replacing each edge i, (i + 1) mod k of the cycle with a connected graph Hi, subject to some constraints on the graphs H_ 0 , . . . , H_ k−1 . In this case we obtain a polynomial lower bound for the new graph H , depending on the size of the shortest cycle in H passing through the vertices of the original k-cycle.