Conjunto universal de puntos

Problemas no resueltos en Matemáticas : ¿Es subcuadrático el tamaño de los conjuntos de puntos universales de gráficos planos?

Un conjunto universal de puntos de orden n es un conjunto S de puntos en el plano euclidiano con la propiedad de que cualquier gráfico plano con n vértices tiene un patrón de borde recto en el que todos los vértices están ubicados en puntos en S .

Límites en las dimensiones del conjunto universal de puntos

Si n es como máximo diez, hay un conjunto universal de puntos que tiene exactamente n puntos, pero para todos los n  ≥ 15 puntos adicionales se requieren [1] .

Algunos autores han demostrado que un subconjunto de una red de enteros de tamaño O ( n ) ×  O ( n ) es universal. En particular, Freysix, Pach y Pollak [2] demostraron que la red (2 n  − 3) × ( n  − 1) es universal, mientras que Schneider [3] redujo la red ( n  − 1) × ( n  − 1) a un subconjunto triangular ) con n 2/2 −  O ( n ) puntos. Al modificar el método de Freysix, Pach y Schneider, Brandenburg [4] encontró una incrustación de cualquier gráfico plano en un subconjunto triangular de una red que contiene 4 n 2/9 puntos. Un conjunto universal de puntos en forma de retícula rectangular debe tener un tamaño de al menos n /3 ×  n /3 [5] , pero esto no excluye la posibilidad de la existencia de un conjunto universal más pequeño de puntos de otro tipo . Los conjuntos de puntos universales más pequeños conocidos no se basan en redes, sino que se construyen a partir de superesquemas ( permutaciones que contienen todas las imágenes de permutaciones de un tamaño determinado). Los conjuntos de puntos universales construidos de esta manera tienen tamaño n 2 /4 −  O ( n ) [6] .

Freysix, Pach y Pollack [2] demostraron el primer límite inferior no trivial del tamaño de un conjunto universal de puntos en la forma n  + Ω(√ n ), mientras que Chrobak y Karloff [7] demostraron que el conjunto universal de puntos debe contener al menos 1.098 n  −  o ( n ) puntos. Kurowski [8] propuso un límite aún más fuerte 1.235 n  −  o ( n ), que sigue siendo el mejor límite inferior [9] .

Cerrar la brecha entre los límites lineales conocidos y los límites superiores cuadráticos sigue siendo un problema abierto [10] .

Clases especiales de grafos

Las subclases de gráficos planos pueden, en general, tener conjuntos universales más pequeños (conjuntos de puntos que permiten dibujar todos los gráficos con n vértices con aristas directas en la subclase) que la clase completa de todos los gráficos planos, y en muchos casos hay puntos universales. conjuntos que tienen n puntos de precisión . Por ejemplo, es fácil ver que cualquier conjunto de n puntos en la posición convexa (que sirven como vértices de un polígono convexo) es universal para grafos planos exteriores de n vértices , y en particular para árboles . Menos obvio, cualquier conjunto de n puntos en posición general (no hay tres que se encuentren en la misma línea) sigue siendo universal para grafos planos exteriores [11] .

Los gráficos planos que se pueden dividir en bucles anidados y los gráficos planos con un ancho de ruta limitado tienen un conjunto universal de puntos de tamaño casi lineal [12] [6] . Los 3 árboles planos tienen conjuntos de puntos universales de tamaño O ( n 5/3 ). El mismo límite se mantiene para los gráficos secuenciales paralelos [13] .

Otros estilos de dibujo

Como en el caso del dibujo de gráficos con bordes rectos, los conjuntos de puntos universales se han estudiado para otros estilos. En la mayoría de estos casos, existen conjuntos de puntos universales que tienen exactamente n puntos, y se basan en una incrustación de libro topológica , en la que los vértices se ubican en una línea en el plano y los bordes se dibujan como curvas que intersecan este. línea como máximo una vez. Por ejemplo, cualquier conjunto de n puntos colineales es universal para un diagrama de arco , en el que cada borde se representa como un solo semicírculo o como una curva suave formada por dos semicírculos [14] .

Se puede demostrar que usando tal arreglo, cualquier curva convexa en el plano contiene un subconjunto de n puntos, lo cual es universal para patrones de polilínea con como máximo una ruptura por borde [15] . Este conjunto contiene solo los vértices del patrón, no los puntos de ruptura. Se conocen conjuntos más grandes que se pueden usar para dibujos que usan líneas quebradas, en los que los vértices y todos los puntos de quiebre son puntos del conjunto [16] .

Notas

  1. ↑ Cardenal, Hoffmann, Kusters, 2015 .
  2. ↑ 1 2 de Fraysseix, Pach y Pollack, 1988 .
  3. ↑ Schnyder, 1990 .
  4. ↑ Brandeburgo, 2008 .
  5. ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak y Karloff 1989 ; Demaine, O'Rourke, 2002–2012 . Valiant (1981 ) proporcionó previamente un límite cuadrático más débil en el tamaño de la red requerida para los dibujos de gráficos planos .
  6. ↑ 1 2 Barandilla, Cheng, Devanny, Eppstein, 2013 .
  7. ↑ Chrobak, Karloff, 1989 .
  8. ↑ Kurowski, 2004 .
  9. ↑ Mondal ( 2012 ) argumentó que la prueba de Kurowski estaba equivocada, pero luego (después de una discusión con Gene Cardinal) se retractó de su afirmación. Consulte la prueba de Kurowski para obtener una explicación . Archivado el 15 de marzo de 2017 en Wayback Machine .
  10. ↑ Demaine, O'Rourke, 2002–2012 ; Brandeburgo, Eppstein, Goodrich, Kobourov, 2003 ; Mohar, 2007 .
  11. ↑ Gritzmann, Mohar, Pach, Pollack, 1991 .
  12. ↑ Angelini, Di Battista, Kaufmann, Mchedlidze, 2012 .
  13. ↑ Fulek, Toth, 2013 .
  14. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007 .
  15. ↑ Everett, Lazard, Liotta, Wismath, 2010 .
  16. ↑ Dujmovic, Evans, Lazard, Lenhart, 2013 .

Literatura