Search

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point $O$ such that every ray emanating from $O$ crosses every edge of the drawing at most once and there is a ray emanating from $O$ which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with $n$ vertices contains $\Omega(n^{\frac{1}{2}})$ pairwise disjoint edges and a plane path of length $\Omega(\frac{\log n }{\log \log n})$. Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest., Comment: 41 pages, 44 figures, this work (without appendix) will be available in the proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022)

Dando continuidad a la larga serie de Encuentros ya celebrados en diferentes ciudades espan ̃olas, los XIII Encuentros de Geometr ́ıa Computacional se han celebrado en Zaragoza, del 29 de junio al 1 de julio de 2009. El objetivo fundamental ha sido potenciar al m ́aximo la colaboraci ́on entre los investigadores del ́area de Geometr ́ıa Computacional, ofreciendo un marco adecuado para la difusi ́on de sus trabajos m ́as recientes. En estas actas se recogen las cinco conferencias invitadas y las veintinueve comunicaciones presentadas en dichos Encuentros. Con ́ellas, se pretende dejar constancia del desarrollo y consolidaci ́on de la disciplina en Espan ̃a, as ́ı como reflejar el creciente inter ́es que suscitan estos Encuentros entre la comunidad internacional, especialmente entre la comunidad hispanohablante. Desde el comit ́e organizador queremos expresar nuestro m ́as sincero agradecimiento a todos aquellos que con su esfuerzo y colaboraci ́on han hecho posible la realizaci ́on de estos Encuentros, y muy especialmente a los participantes, sin cuyos trabajos y aportaciones hubiese sido imposible alcanzar los objetivos de estos Encuentros. Por u ́ltimo, agradecer tambi ́en a la Universidad de Zaragoza, al Departamento de M ́etodos Estad ́ısticos, la Facultad de Ciencias y el Instituto Universitario de Matem ́aticas y Aplicaciones de dicha Universidad, a la Real Sociedad Matem ́atica Espan ̃ola, al proyecto Ingenio Mathematica, a la Diputaci ́on General de Arag ́on y al Ministerio de Ciencia y Tecnolog ́ıa los diferentes apoyos recibidos.

We say that a finite set of red and blue points in the plane in general position can be $K_{1,3}$-covered if the set can be partitioned into subsets of size $4$, with $3$ points of one color and $1$ point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set $R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general position, how many points of $R\cup B$ can be $K_{1,3}$-covered? and we prove the following results: (1) If $r=3g+h$ and $b=3h+g$, for some non-negative integers $g$ and $h$, then there are point sets $R\cup B$, like $\{1,3\}$-equitable sets (i.e., $r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$-covered. (2) If $r=3g+h$, $b=3h+g$ and the points in $R\cup B$ are in convex position, then at least $r+b-4$ points can be $K_{1,3}$-covered, and this bound is tight. (3) There are arbitrarily large point sets $R\cup B$ in general position, with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered. (4) If $b\le r\le 3b$, then at least $\frac{8}{9}(r+b-8)$ points of $R\cup B$ can be $K_{1,3}$-covered. For $r>3b$, there are too many red points and at least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings., Discrete Mathematics & Theoretical Computer Science ; Vol. 21 no. 3 ; 1365-8050