More Like this

1. Polygons with Prescribed Angles in 2D and 3D

   Efrat, A; Fulek, R; Kobourov, S; Toth, C (October 2020, 28th International Symposium on Graph Drawing and Network Visualization (GD))

   We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A = (α0 , . . . , αn−1 ), αi ∈ (−π,π), for i ∈ {0,...,n − 1}. The problem of realizing A by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P ⊂ R2 realizing A has at least c crossings, and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P ⊂ R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P ⊂ R3, and for every realizable sequence finds a realization. 

   more » « less
2. Universal Geometric Graphs

   https://doi.org/10.1007/978-3-030-60440-0_14  

   Frati, Fabrizio; Hoffmann, Michael; Toth, Csaba D. (October 2020, Graph-Theoretic Concepts in Computer Science (WG 2020))

   null (Ed.)

   We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars. 

   more » « less
3. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng; Rudelson, Mark; Tikhomirov, Konstantin (August 2021, Proceedings of Machine Learning Research)

   Belkin, Mikhail; Kpotufe, Samory (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation $$1-\alpha$$, our algorithm recovers the underlying matching exactly with high probability when $$\alpha \le 1 / (\log \log n)^C$$, where $$n$$ is the number of vertices in each graph and $$C$$ denotes a positive universal constant. This improves the condition $$\alpha \le 1 / (\log n)^C$$ achieved in previous work. 

   more » « less
4. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng; Rudelson, Mark; Tikhomirov, Konstantin (July 2021, Proceedings of Thirty Fourth Conference on Learning Theory)

   Belkin, Mikhail; Samory Kpotufe (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation 1−α, our algorithm recovers the underlying matching exactly with high probability when α≤1/(loglogn)C, where n is the number of vertices in each graph and C denotes a positive universal constant. This improves the condition α≤1/(logn)C achieved in previous work. 

   more » « less
5. An Exact Geometry–Based Algorithm for Path Planning

   https://doi.org/10.2478/amcs-2018-0038  

   Jafarzadeh, Hassan; Fleming, Cody H. (September 2018, International Journal of Applied Mathematics and Computer Science)

   null (Ed.)

   Abstract A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn r2 ) time, where n is the number of vertices of all polygons and n ̓ is the number of vertices that are considered in constructing the path network (n ̓ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically. 

   more » « less