Using graphs to understand opinions

In the last few years, the use of graph techniques has provided new approaches to the collection and analysis of opinions. The fields of application range from food preference to acquisition of mathematical notions in kindergarten. This talk will review some of the techniques and results used, aiming that the audience can identify other possible areas of application.

Computational complexity of finding perfect rainbow polygons.

Let \(S\) be a \(k\)-colored point set in the plane in general position (no three points on the same line). A perfect rainbow polygon on \(S\) is a simple polygon that contains exactly one point of \(S\) of each of the \(k\) colors, either on its interior or on its boundary.

In [D. Flores-Penaloza, M. Kano, L. Martínez-Sandoval, D. Orden, J. Tejel, C.D. Tóth, J. Urrutia, B. Vogtenhuber. Rainbow polygons for colored point sets in the plane, Discrete Mathematics, 334(7), 2021], the authors define and study the combinatorial problem of determining the number rb-index(\(k\)): the smallest integer such that every \(k\) colored point set in general position has a perfect rainbow polygon with at most rb-index(\(k\)) vertices. They conjecture that the following related problem is NP-Hard:

Given a \(k\)-colored point set \(S\) in general position, and a positive integer \(v\), decide whether there exists a perfect rainbow polygon on \(S\) with at most \(v\) vertices.

We prove this conjecture is true, reducing from one-in-three 3-SAT.

Voronoi Diagrams of Arbitrary Order on the Sphere

For a given set of points \(U\) on a sphere \(S\), the order \(k\) spherical Voronoi diagram \(SV_k(U)\) decomposes the surface of \(S\) into regions whose points have the same \(k\) nearest points of \(U\). Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct \(SV_1(U)\). We generalize their construction for spherical Voronoi diagrams from order \(1\) to any order \(k\). We use that construction to prove formulas for the numbers of vertices, edges, and faces in \(SV_k(U)\). These formulas were not known before. We obtain several more properties for \(SV_k(U)\), and we also show that \(SV_k(U)\) has a small orientable cycle double cover.