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. Asymptotics of Closeness Centralities of Graphs

   https://doi.org/10.3390/math13233812  

   Frias, Santiago; Galindo_Silva, Adriana; Romero, Bryan; Narayan, Darren A (December 2025, Mathematics)

   Given a connected graph G with n vertices, the distance between two vertices is the number of edges in a shortest path connecting them. The sum of the distances in a graph G from a vertex v to all other vertices is denoted by SDG(v). The closeness centrality of a vertex in a graph was defined by Bavelas to be CC(v)=n−1SDG(v) and the closeness centrality of G is CC(G)=∑v∈Gn−1SDG(v). We consider the asymptotic limit of CC(G) as the number of vertices tends to infinity and provide an elegant and insightful proof of a 2025 result by Britz, Hu, Islam, and Tang, limn→∞CC(Pn)=π, using uniform convergence and Riemann sums. We applied the same technique for the union of a cycle Cm and path Pn and the union of a path and a complete graph. We prove that of all graphs, paths have the minimum closeness centrality. Next we show for any c∈[π,∞), there exists a sequence of graphs {Gn} such that limn→∞CC(Gn)=c. In addition, we investigate the mean distance of a graph, l¯(G)=1n(n−1)∑v∈V(G)SD(v) and the normalized closeness centrality, C¯C(G)=1nCC(G). We verify a conjecture of Britz, Hu, Islam, and Tang that the set of products {l¯(G)C¯C(G):Gisfiniteandconnected} is dense in [1,2). 

   more » « less
3. 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
4. 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
5. 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