7 papers
Uniform Geodesic Drawings of Graphs
Saba Lepsveridze, Oriol Solé-Pi
We study crossing numbers of dense graph drawings whose vertices are uniformly distributed either on the unit sphere or in a compact convex planar domain. We prove a sharp inequali…
There are many 5-holes
Omar Astudillo-Marbán, Oriol Solé-Pi
Given a set P of points on the plane, a polygon with vertices in P is said to be empty if it contains no element of P in its interior. We show that every set of n points in general…
Minor-excluded graphs and soficity
Oriol Solé-Pi
A random rooted graph is said to be sofic if it is the Benjamini-Schramm limit of a sequence of finite graphs. Given any finite graph , we prove that every one-ended, unimodular…
Sharp threshold for network recovery from voter model dynamics
Hang Du, Seokmin Ha, Oriol Solé-Pi
We investigate the problem of recovering a latent directed ErdÅs-Rényi graph from observations of discrete voter model trajectories on , where …
Ortho-unit polygons can be guarded with at most guards
J. M. DÃaz-Báñez, P. Horn, M. A. Lopez +5
An orthogonal polygon is called an ortho-unit polygon if its vertices have integer coordinates, and all of its edges have length one. In this paper we prove that any ortho-unit pol…
An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers
Oriol Solé-Pi
We present a deterministic -time algorithm that approximates the crossing number of any graph of order up to an additive error of . We also provide a ra…