Aktuální informace FIT ke koronaviru najdete zde.

MSc. Maria Saumell Mendiola, Ph.D.

Publikace

Hamiltonicity for convex shape Delaunay and Gabriel graphs

Autoři
Saumell Mendiola, M.; Bose, P.; Cano, P.; Silveira, R.
Rok
2020
Publikováno
Computational Geometry: Theory and Applications. 2020, 2020(89), ISSN 0925-7721.
Typ
Článek
Anotace
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape $\mathcal{C}$. Let $S$ be a point set in the plane. The $k$-order Delaunay graph of $S$, denoted $k$-${DG}_{\mathcal{C}}(S)$, has vertex set $S$, and edges defined as follows. Given $p, q \in S$, $pq$ is an edge of $k$-${DG}_{\mathcal{C}}(S)$ provided there exists \emph{some} homothet of $\mathcal{C}$ with $p$ and $q$ on its boundary and containing at most $k$ points of $S$ different from $p$ and $q$. The $k$-order Gabriel graph, denoted $k$-${GG}_{\mathcal{C}}(S)$, is defined analogously, except that the homothets considered are restricted to be \emph{smallest} homothets of $\mathcal{C}$ with $p$ and $q$ on the boundary. We provide upper bounds on the minimum value of $k$ for which $k$-${GG}_{\mathcal{C}}(S)$ is Hamiltonian. Since $k$-${GG}_{\mathcal{C}}(S)$ $\subseteq$ $k$-${DG}_{\mathcal{C}}(S)$, all results carry over to $k$-${DG}_{\mathcal{C}}(S)$. In particular, we give upper bounds of 24 for every $\mathcal{C}$ and 15 for every point-symmetric $\mathcal{C}$. We also improve these bounds to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular $t$-gons (for $t \geq 10)$. These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. In addition, we show lower bounds of $k=3$ and $k=6$ on the existence of a bottleneck Hamiltonian cycle in the $k$-order Gabriel graph for squares and hexagons, respectively. Finally, we construct a point set such that for an infinite family of regular polygons $\mathcal{P}_t$, the Delaunay graph ${DG}_{\mathcal{P}_t}$ does not contain a Hamiltonian cycle.

A median-type condition for graph tiling

Autoři
Saumell Mendiola, M.; Piguet, D.
Rok
2019
Publikováno
European Journal of Combinatorics. 2019, 77 90-101. ISSN 1095-9971.
Typ
Článek
Anotace
Komlós (2000) determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree.

Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs

Autoři
Saumell Mendiola, M.; Bose, P.; Cano, P.; Silveira, R.I.
Rok
2019
Publikováno
16th International Symposium on Algorithms and Data Structures (WADS 2019). Cham: Springer, 2019. p. 196-210. vol. 11646. ISSN 0302-9743. ISBN 978-3-030-24765-2.
Typ
Stať ve sborníku
Anotace
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DG_C(S), has vertex set S and edge pq provided that there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k-GG_C(S) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of C with p and q on its boundary. We provide upper bounds on the minimum value of k for which k-GG_C(S) is Hamiltonian. Since k-GG_C(S)⊆k-DG_C(S), all results carry over to k-DG_C(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t≥10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs.

Minimal Obstructions for Partial Representations of Interval Graphs

Autoři
Saumell Mendiola, M.; Klavik, P.
Rok
2018
Publikováno
Electronic Journal of Combinatorics (E-JC),. 2018, 25(4), ISSN 1077-8926.
Typ
Článek
Anotace
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.