Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 5
Encontrada(s) 1 página(s)

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Maximum rectilinear convex subsets

  • Gonzalez-Aguilar, H.
  • Orden, D.
  • Perez-Lantero, P.
  • Rappaport, D.
  • Seara, C.
  • Tejel, J.
  • Urrutia, J.
Let P be a set of n points in the plane. We consider a variation of the classical Erd\H os-Szekeres problem, presenting efficient algorithms with O(n3) running time and O(n2) space complexity that compute (1) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P, (2) a subset S of P such that the boundary of the rectilinear convex hull of S has the maximum number of points from P and its interior contains no element of P, (3) a subset S of P such that the rectilinear convex hull of S has maximum area and its interior contains no element of P, and (4) when each point of P is assigned a weight, positive or negative, a subset S of P that maximizes the total weight of the points in the rectilinear convex hull of S. We also revisit the problems of computing a maximum area orthoconvex polygon and computing a maximum area staircase polygon, amidst a point set in a rectangular domain. We obtain new and simpler algorithms to solve both problems with the same complexity as in the state of the art.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

On plane subgraphs of complete topological drawings

  • García Olaverri A.
  • Tejel Altarriba J.
  • Pilz A.
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dnof the complete graph Knon n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least [3n/2] edges. We also address the problem of obtaining a plane subgraph of Dnwith the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete. © 2021 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Rainbow polygons for colored point sets in the plane

  • Flores-Peñaloza D.
  • Kano M.
  • Martínez-Sandoval L.
  • Orden D.
  • Tejel J.
  • Tóth C.D.
  • Urrutia J.
  • Vogtenhuber B.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let rb-index(S) denote the smallest size of a perfect rainbow polygon for a colored point set S, and let rb-index(k) be the maximum of rb-index(S) over all k-colored point sets in general position; that is, every k-colored point set S has a perfect rainbow polygon with at most rb-index(k) vertices. In this paper, we determine the values of rb-index(k) up to k=7, which is the first case where rb-index(k)¿k, and we prove that for k=5, [Formula presented] Furthermore, for a k-colored set of n points in the plane in general position, a perfect rainbow polygon with at most [Formula presented] vertices can be computed in O(nlogn) time. © 2021 Elsevier B.V.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

  • Aichholzer, Oswin
  • García, Alfredo
  • Tejel, Javier
  • Vogtenhuber, Birgit
  • Weinberger, Alexandra
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 Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((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.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Twisted ways to find plane structures in simple drawings of complete graphs

  • Aichholzer, Oswin
  • García, Alfredo
  • Tejel, Javier
  • Vogtenhuber, Birgit
  • Weinberger, Alexandra
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). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains [fórmula] pairwise disjoint edges and a plane cycle (and hence path) of length [fórmula]. Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.