6 papers · 1 filter
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…
On the crossing profile of rectilinear drawings of
Isaac Chen, Oriol Solé-Pi
We introduce the \textit{crossing profile} of a drawing of a graph. This is a sequence of integers whose entry counts the number of edges in the drawing which a…
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…
Crossing and intersecting families of geometric graphs on point sets
José Luis Álvarez-Rebollar, Jorge Cravioto-Lagos, Nestaly Marín +2
Let be a set of points in the plane in general position. Two line segments connecting pairs of points of cross if they have an interior point in common. Two vertex disj…