More Like this

1. Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?

   https://doi.org/10.4230/LIPIcs.ITCS.2024.12  

   Bernstein, Aaron; Bodwin, Greg; Wein, Nicole (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   The aspect ratio of a (positively) weighted graph G is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest paths. Popular paradigms are to interpolate between the settings of weighted and unweighted input graphs by incurring a dependence on aspect ratio, or by simply restricting attention to input graphs of low aspect ratio. This paper studies the effects of these paradigms, investigating whether graphs of low aspect ratio have more structured shortest paths than graphs in general. In particular, we raise the question of whether one can generally take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths. Our findings are: - Every weighted DAG on n nodes has a shortest-paths preserving graph of aspect ratio O(n). A simple lower bound shows that this is tight. - The previous result does not extend to general directed or undirected graphs; in fact, the answer turns out to be exponential in these settings. In particular, we construct directed and undirected n-node graphs for which any shortest-paths preserving graph has aspect ratio 2^{Ω(n)}. We also consider the approximate version of this problem, where the goal is for shortest paths in H to correspond to approximate shortest paths in G. We show that our exponential lower bounds extend even to this setting. We also show that in a closely related model, where approximate shortest paths in H must also correspond to approximate shortest paths in G, even DAGs require exponential aspect ratio. 

   more » « less
2. The effect of adding randomly weighted edges

   https://doi.org/10.1137/20M1335418  

   Frieze, A. (January 2021, SIAM journal on discrete mathematics)

   We consider the following question. We have a dense regular graph $$G$$ with degree $$\a n$$, where $$\a>0$$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $$X(e),e\in E(G(m))$$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $$\a^{-1}$$. We consider spanning trees, shortest paths and perfect matchings in (pseudo-random) bipartite graphs. 

   more » « less
3. Noncrossing Longest Paths and Cycles

   https://doi.org/10.4230/LIPIcs.GD.2024.36  

   Aloupis, Greg; Biniaz, Ahmad; Bose, Prosenjit; De_Carufel, Jean-Lou; Eppstein, David; Maheshwari, Anil; Odak, Saeed; Smid, Michiel; Tóth, Csaba D; Valtr, Pavel (October 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Felsner, Stefan; Klein, Karsten (Ed.)

   Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing. 

   more » « less
4. Simple Topological Drawings of k-Planar Graphs.

   https://doi.org/10.1007/978-3-030-68766-3_31  

   Hoffmann, Michael; Liu, Chih-Hung; Reddy, Meghana M.; Toth, Csaba D. (February 2021, Graph Drawing and Network Visualization)

   null (Ed.)

   Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for k≤3 , every k-planar graph admits a k-plane simple drawing. But for k≥4 , there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every k-planar graph admits an f(k)-plane simple drawing, for all Open image in new window. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4-planar graph admits an 8-plane simple drawing. 

   more » « less
5. Factorization and pseudofactorization of weighted graphs

   Kristin Sheridan, Joseph Berleant (July 2023, Discrete applied mathematics)

   For unweighted graphs, finding isometric embeddings of a graph G is closely related to decompositions of G into Cartesian products of smaller graphs. When G is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of G. When G is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of G. Prior work has shown that an unweighted graph’s pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph G, where G satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, ’85] and Feder [Feder, ’92] for pseudofactorization and factorization of unweighted graphs. We show that any n-vertex, m-edge graph with positive integer edge weights can be factored in O(m2) time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of O(m2+n2 log log n) time. We also show that a pseudofactorization for such a graph can be computed in O(mn) time, plus the time to solve APSP, resulting in an O(mn + n2 log log n) running time. 

   more » « less