Source author record

Ruy Fabila-Monroy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

23works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Connected ( $C_4$ ,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs

A diamond is the graph that is obtained from removing an edge from the complete graph on $4$ vertices. A ( $C_4$ ,diamond)-free graph is a graph that does not contain a diamond or a cycle on four vertices as induced subgraphs. Let $G$ be a connected ( $C_4$ ,diamond)-free graph on $n$ vertices. Let $1 \le k \le n-1$ be an integer. The $k$ -token graph, $F_k(G)$ , of $G$ is the graph whose vertices are all the sets of $k$ vertices of $G$ ; two of which are adjacent if their symmetric difference is a pair of adjacent vertices in $G$ . Let $F$ be a graph isomorphic to $F_k(G)$ . In this paper we show that given only $F$ , we can construct in polynomial time a graph isomorphic to $G$ . Let $\operatorname{Aut}(G)$ be the automorphism group of $G$ . We also show that if $k\neq n/2$ , then $\operatorname{Aut}(G) \simeq \operatorname{Aut}(F_k(G))$ ; and if $k = n/2$ , then $\operatorname{Aut}(G) \simeq \operatorname{Aut}(F_k(G)) \times \mathbb{Z}_2$ .

preprint2020arXiv

A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$

Let $S$ be a set of $n$ red and $n$ blue points in general position in $\mathbb{R}^3$ . Let $τ$ be a tetrahedra with vertices on $S$ . We say that $τ$ is \emph{empty} if it does not contain any point of $S$ in its interior. We say that $τ$ is \emph{balanced} if it contains two blue vertices and two red vertices. In this paper we show that $S$ spans $Ω(n^{5/2})$ empty balanced tetrahedra.

preprint2020arXiv

An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

A drawing of a graph in the plane is {\it pseudolinear} if the edges of the drawing can be extended to doubly-infinite curves that form an arrangement of pseudolines, that is, any pair of edges crosses precisely once. A special case are {\it rectilinear} drawings where the edges of the graph are drawn as straight line segments. The rectilinear (pseudolinear) crossing number of a graph is the minimum number of pairs of edges of the graph that cross in any of its rectilinear (pseudolinear) drawings. In this paper we describe an ongoing project to continuously obtain better asymptotic upper bounds on the rectilinear and pseudolinear crossing number of the complete graph $K_n$ .

preprint2020arXiv

Chirotopes of Random Points in Space are Realizable on a Small Integer Grid

We prove that with high probability, a uniform sample of $n$ points in a convex domain in $\mathbb{R}^d$ can be rounded to points on a grid of step size proportional to $1/n^{d+1+ε}$ without changing the underlying chirotope (oriented matroid). Therefore, chirotopes of random point sets can be encoded with $O(n\log n)$ bits. This is in stark contrast to the worst case, where the grid may be forced to have step size $1/2^{2^{Ω(n)}}$ even for $d=2$ . This result is a high-dimensional generalization of previous results on order types of random planar point sets due to Fabila-Monroy and Huemer (2017) and Devillers, Duchon, Glisse, and Goaoc (2018).

preprint2020arXiv

Counting the Number of Crossings in Geometric Graphs

A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an $O(n^2 \log n)$ algorithm to compute the number of pairs of edges that cross in a geometric graph on $n$ points. For layered, and convex geometric graphs the algorithm takes $O(n^2)$ time.

preprint2020arXiv

Empty Rainbow Triangles in $k$ -colored Point Sets

Let $S$ be a set of $n$ points in general position in the plane. Suppose that each point of $S$ has been assigned one of $k \ge 3$ possible colors and that there is the same number, $m$ , of points of each color class. A polygon with vertices on $S$ is empty if it does not contain points of $S$ in its interior; and it is rainbow if all its vertices have different colors. Let $f(k,m)$ be the minimum number of empty rainbow triangles determined by $S$ . In this paper we give tight asymptotic bounds for this function. Furthermore, we show that $S$ may not determine an empty rainbow quadrilateral for some arbitrarily large values of $k$ and $m$ .

preprint2020arXiv

Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2\ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k-2$ ; it is called decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k-2$ . We say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$ in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let $G$ be a graph. In a straight-line drawing $D$ of $G$ , its vertices are drawn as different points in the plane and its edges are straight line segments. Let $\overlineα(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $\overlineα(G)$ . Let $\overlineτ(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $\overlineτ(G)$ . In this paper we show that $\overline α(K_n) = Ω(\log\log n)$ , $\overline α(K_n) = O(\log n)$ , $\overline τ(K_n) = Ω(\log\log \log n)$ and $\overline τ(K_n) = O(\sqrt{n \log n})$ .

preprint2016arXiv

Drawing the Almost Convex Set in an Integer Grid of Minimum Size

In 2001, Károlyi, Pach and Tóth introduced a family of point sets to solve an Erdős-Szekeres type problem; which have been used to solve several other Edős-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set $\mathcal{X}$ has the property that the interior of every triangle determined by three points in the same convex layer of $\mathcal{X}$ , contains exactly one point of $\mathcal{X}$ . In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of $n$ points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of $n$ points, with integer coordinates of absolute values at most $O(n^{\log_2 5})$ . Finally, we use our characterization to obtain an $O(n\log n)$ -time algorithm to determine whether a set of points is a nested almost convex set.

preprint2015arXiv

Modem Illumination of Monotone Polygons

We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$ -modems and study the minimum number of $k$ -modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $\big\lceil \frac{n-2}{2k+3} \big\rceil$ $k$ -modems. In addition, we exhibit examples of monotone polygons requiring at least $\lceil \frac {n-2} {2k+3}\rceil$ $k$ -modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$ , every such polygon can be illuminated with $\big\lceil \frac{n-2}{2k+4} \big\rceil$ $k$ -modems, while for odd $k\geq3$ , $\big\lceil \frac{n-2}{2k+6} \big\rceil$ $k$ -modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight.

preprint2014arXiv

$(n,m)$ -Fold Covers of Spheres

A well known consequence of the Borsuk-Ulam theorem is that if the $d$ -dimensional sphere $S^d$ is covered with less than $d+2$ open sets, then there is a set containing a pair of antipodal points. In this paper we provide lower and upper bounds on the minimum number of open sets, not containing a pair of antipodal points, needed to cover the $d$ -dimensional sphere $n$ times, with the additional property that the northern hemisphere is covered $m > n$ times. We prove that if the open northern hemisphere is to be covered $m$ times then at least $\lceil \frac{d-1}{2} \rceil+n+m$ and at most $d+n+m$ sets are needed. For the case of $n=1$ and $d \ge 2$ , this number is equal to $d+2$ if $m \le \lfloor \frac{d}{2} \rfloor + 1$ and equal to $\lfloor \frac{d-1}{2} \rfloor + 2 +m$ if $m > \lfloor \frac{d}{2} \rfloor + 1$ . If the closed northern hemisphere is to be covered $m$ times then $d+2m-1$ sets are needed, this number is also sufficient. We also present results on a related problem of independent interest. We prove that if $S^d$ is covered $n$ times with open sets, not containing a pair of antipodal points, then there exists a point that is covered at least $\lceil \frac{d}{2} \rceil +n$ times. Furthermore, we show that there are covers in which no point is covered more than $n+d$ times.

preprint2014arXiv

Computational search of small point sets with small rectilinear crossing number

Let $\crs(K_n)$ be the minimum number of crossings over all rectilinear drawings of the complete graph on $n$ vertices on the plane. In this paper we prove that $\crs(K_n) < 0.380473\binom{n}{4}+Θ(n^3)$; improving thus on the previous best known upper bound. This is done by obtaining new rectilinear drawings of $K_n$ for small values of $n$ , and then using known constructions to obtain arbitrarily large good drawings from smaller ones. The "small" sets where found using a simple heuristic detailed in this paper.

preprint2014arXiv

On $k$ -Gons and $k$ -Holes in Point Sets

We consider a variation of the classical Erdős-Szekeres problems on the existence and number of convex $k$ -gons and $k$ -holes (empty $k$ -gons) in a set of $n$ points in the plane. Allowing the $k$ -gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$ , we give a quadratic lower bound for the number of $k$ -holes, and show that this number is maximized by sets in convex position.

preprint2013arXiv

Drawing the double circle on a grid of minimum size

In 1926, Jarník introduced the problem of drawing a convex $n$ -gon with vertices having integer coordinates. He constructed such a drawing in the grid $[1,c\cdot n^{3/2}]^2$ for some constant $c>0$ , and showed that this grid size is optimal up to a constant factor. We consider the analogous problem for drawing the double circle, and prove that it can be done within the same grid size. Moreover, we give an O(n)-time algorithm to construct such a point set.

preprint2012arXiv

Decompositions of Complete Multipartite Graphs into Complete Graphs

Let $k\geq\ell\geq1$ and $n\geq 1$ be integers. Let $G(k,n)$ be the complete $k$ -partite graph with $n$ vertices in each colour class. An $\ell$ -decomposition of $G(k,n)$ is a set $X$ of copies of $K_k$ in $G(k,n)$ such that each copy of $K_\ell$ in $G(k,n)$ is a subgraph of exactly one copy of $K_k$ in $X$ . This paper asks: when does $G(k,n)$ have an $\ell$ -decomposition? The answer is well known for the $\ell=2$ case. In particular, $G(k,n)$ has a 2-decomposition if and only if there exists $k-2$ mutually orthogonal Latin squares of order $n$ . For general $\ell$ , we prove that $G(k,n)$ has an $\ell$ -decomposition if and only if there are $k-\ell$ Latin cubes of dimension $\ell$ and order $n$ , with an additional property that we call mutually invertible. This property is stronger than being mutually orthogonal. An $\ell$ -decomposition of $G(k,n)$ is then constructed whenever no prime less than $k$ divides $n$ .

preprint2012arXiv

Empty Monochromatic Simplices

Let $S$ be a $k$ -colored (finite) set of $n$ points in $\mathbb{R}^d$ , $d\geq 3$ , in general position, that is, no { $(d + 1)$ } points of $S$ lie in a common $(d - 1)$ }-dimensional hyperplane. We count the number of empty monochromatic $d$ -simplices determined by $S$ , that is, simplices which have only points from one color class of $S$ as vertices and no points of $S$ in their interior. For $3 \leq k \leq d$ we provide a lower bound of $Ω(n^{d-k+1+2^{-d}})$ and strengthen this to $Ω(n^{d-2/3})$ for $k=2$ . On the way we provide various results on triangulations of point sets in $\mathbb{R}^d$ . In particular, for any constant dimension $d\geq3$ , we prove that every set of $n$ points ( $n$ sufficiently large), in general position in $\mathbb{R}^d$ , admits a triangulation with at least $dn+Ω(\log n)$ simplices.

preprint2012arXiv

Hamiltonian Tetrahedralizations with Steiner Points

Let $S$ be a set of $n$ points in 3-dimensional space. A tetrahedralization $\mathcal{T}$ of $S$ is a set of interior disjoint tetrahedra with vertices on $S$ , not containing points of $S$ in their interior, and such that their union is the convex hull of $S$ . Given $\mathcal{T}$ , $D_\mathcal{T}$ is defined as the graph having as vertex set the tetrahedra of $\mathcal{T}$ , two of which are adjacent if they share a face. We say that $\mathcal{T}$ is Hamiltonian if $D_\mathcal{T}$ has a Hamiltonian path. Let $m$ be the number of convex hull vertices of $S$ . We prove that by adding at most $\lfloor \frac{m-2}{2} \rfloor$ Steiner points to interior of the convex hull of $S$ , we can obtain a point set that admits a Hamiltonian tetrahedralization. An $O(m^{3/2}) + O(n \log n)$ time algorithm to obtain these points is given. We also show that all point sets with at most 20 convex hull points admit a Hamiltonian tetrahedralization without the addition of any Steiner points. Finally we exhibit a set of 84 points that does not admit a Hamiltonian tetrahedralization in which all tetrahedra share a vertex.

preprint2012arXiv

On the Connectedness and Diameter of a Geometric Johnson Graph

Let $P$ be a set of $n$ points in general position in the plane. A subset $I$ of $P$ is called an \emph{island} if there exists a convex set $C$ such that $I = P \cap C$ . In this paper we define the \emph{generalized island Johnson graph} of $P$ as the graph whose vertex consists of all islands of $P$ of cardinality $k$ , two of which are adjacent if their intersection consists of exactly $l$ elements. We show that for large enough values of $n$ , this graph is connected, and give upper and lower bounds on its diameter.

preprint2012arXiv

On the number of radial orderings of planar point sets

Given a set $S$ of $n$ points in the plane, a \emph{radial ordering} of $S$ with respect to a point $p$ (not in $S$ ) is a clockwise circular ordering of the elements in $S$ by angle around $p$ . If $S$ is two-colored, a \emph{colored radial ordering} is a radial ordering of $S$ in which only the colors of the points are considered. In this paper, we obtain bounds on the number of distinct non-colored and colored radial orderings of $S$ . We assume a strong general position on $S$ , not three points are collinear and not three lines---each passing through a pair of points in $S$ ---intersect in a point of $\R^2\setminus S$ . In the colored case, $S$ is a set of $2n$ points partitioned into $n$ red and $n$ blue points, and $n$ is even. We prove that: the number of distinct radial orderings of $S$ is at most $O(n^4)$ and at least $Ω(n^3)$ ; the number of colored radial orderings of $S$ is at most $O(n^4)$ and at least $Ω(n)$ ; there exist sets of points with $Θ(n^4)$ colored radial orderings and sets of points with only $O(n^2)$ colored radial orderings.

preprint2012arXiv

The Erdős-Sós Conjecture for Geometric Graphs

Let $f(n,k)$ be the minimum number of edges that must be removed from some complete geometric graph $G$ on $n$ points, so that there exists a tree on $k$ vertices that is no longer a planar subgraph of $G$ . In this paper we show that $(1/2)\frac{n^2}{k-1}-\frac{n}{2}\le f(n,k) \le 2 \frac{n(n-2)}{k-2}$ . For the case when $k=n$ , we show that $2 \le f(n,n) \le 3$ . For the case when $k=n$ and $G$ is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.

preprint2011arXiv

Colouring the Triangles Determined by a Point Set

Let P be a set of n points in general position in the plane. We study the chromatic number of the intersection graph of the open triangles determined by P. It is known that this chromatic number is at least n^3/27+O(n^2), and if P is in convex position, the answer is n^3/24+O(n^2). We prove that for arbitrary P, the chromatic number is at most n^3/19.259+O(n^2).

preprint2011arXiv

Rooted $K_4$ -Minors

Let $a,b,c,d$ be four vertices in a graph $G$ . A \emph{ $K_4$ -minor rooted} at $a,b,c,d$ consists of four pairwise-disjoint pairwise-adjacent connected subgraphs of $G$ , respectively containing $a,b,c,d$ . We characterise precisely when $G$ contains a $K_4$ -minor rooted at $a,b,c,d$ by describing six classes of obstructions, which are the edge-maximal graphs containing no $K_4$ -minor rooted at $a,b,c,d$ . The following two special cases illustrate the full characterisation: (1) A 4-connected non-planar graph contains a $K_4$ -minor rooted at $a,b,c,d$ for every choice of $a,b,c,d$ . (2) A 3-connected planar graph contains a $K_4$ -minor rooted at $a,b,c,d$ if and only if $a,b,c,d$ are not on a single face.

preprint2011arXiv

The chromatic number of the convex segment disjointness graph

Let $P$ be a set of $n$ points in general and convex position in the plane. Let $D_n$ be the graph whose vertex set is the set of all line segments with endpoints in $P$ , where disjoint segments are adjacent. The chromatic number of this graph was first studied by Araujo et al. [\emph{CGTA}, 2005]. The previous best bounds are $\frac{3n}{4}\leqχ(D_n) <n-\sqrt{\frac{n}{2}}$ (ignoring lower order terms). In this paper we improve the lower bound to $χ(D_n)\geq n-\sqrt{2n}$ , to conclude a near-tight bound on $χ(D_n)$ .

preprint2009arXiv

Token Graphs

For a graph $G$ and integer $k\geq1$ , we define the token graph $F_k(G)$ to be the graph with vertex set all $k$ -subsets of $V(G)$ , where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is a pair of adjacent vertices in $G$ . Thus vertices of $F_k(G)$ correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$ , where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ruy Fabila-Monroy

Research overview

Is this your work?

23 publications

Connected ( $C_4$ ,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs

A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$

An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

Chirotopes of Random Points in Space are Realizable on a Small Integer Grid

Counting the Number of Crossings in Geometric Graphs

Empty Rainbow Triangles in $k$ -colored Point Sets

Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

Drawing the Almost Convex Set in an Integer Grid of Minimum Size

Modem Illumination of Monotone Polygons

$(n,m)$ -Fold Covers of Spheres

Computational search of small point sets with small rectilinear crossing number

On $k$ -Gons and $k$ -Holes in Point Sets

Drawing the double circle on a grid of minimum size

Decompositions of Complete Multipartite Graphs into Complete Graphs

Empty Monochromatic Simplices

Hamiltonian Tetrahedralizations with Steiner Points

On the Connectedness and Diameter of a Geometric Johnson Graph

On the number of radial orderings of planar point sets

The Erdős-Sós Conjecture for Geometric Graphs

Colouring the Triangles Determined by a Point Set

Rooted $K_4$ -Minors

The chromatic number of the convex segment disjointness graph

Token Graphs

See the researcher in context

Building this map preview

Ruy Fabila-Monroy

Research overview

Is this your work?

23 publications

Connected (C4C_4C4​,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs

A Note on Empty Balanced Tetrahedra in Two colored Point sets in R3\mathbb{R}^3R3

An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

Chirotopes of Random Points in Space are Realizable on a Small Integer Grid

Counting the Number of Crossings in Geometric Graphs

Empty Rainbow Triangles in kkk-colored Point Sets

Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

Drawing the Almost Convex Set in an Integer Grid of Minimum Size

Modem Illumination of Monotone Polygons

(n,m)(n,m)(n,m)-Fold Covers of Spheres

Computational search of small point sets with small rectilinear crossing number

On kkk-Gons and kkk-Holes in Point Sets

Drawing the double circle on a grid of minimum size

Decompositions of Complete Multipartite Graphs into Complete Graphs

Empty Monochromatic Simplices

Hamiltonian Tetrahedralizations with Steiner Points

On the Connectedness and Diameter of a Geometric Johnson Graph

On the number of radial orderings of planar point sets

The Erdős-Sós Conjecture for Geometric Graphs

Colouring the Triangles Determined by a Point Set

Rooted K4K_4K4​-Minors

The chromatic number of the convex segment disjointness graph

Token Graphs

See the researcher in context

Building this map preview

Connected ( $C_4$ ,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs

A Note on Empty Balanced Tetrahedra in Two colored Point sets in $\mathbb{R}^3$

Empty Rainbow Triangles in $k$ -colored Point Sets

$(n,m)$ -Fold Covers of Spheres

On $k$ -Gons and $k$ -Holes in Point Sets

Rooted $K_4$ -Minors