Conjunto de puntos universal

En el dibujo de grafos , un conjunto de puntos universal de orden n es un conjunto S de puntos en el plano euclidiano con la propiedad de que todo grafo planar de n vértices tiene un dibujo de línea recta en el que todos los vértices están colocados en puntos de S.

Cuando n ≤ 10, existen conjuntos de puntos universales con exactamente n puntos, pero para todo n  ≥  15 se requieren puntos adicionales. ^{[ 1 ]}

Varios autores han demostrado que los subconjuntos de la red entera de tamaño O ( n )  × O ( n ) son universales. En particular, de Fraysseix, Pach y Pollack (1988) demostraron que una cuadrícula de (2n − 3 ) × ( n − 1) puntos es universal, y Schnyder (1990) la redujo a un subconjunto triangular de una cuadrícula de ( n − 1) × ( n − 1), con n² /2 ⁻ O ( n ) puntos. Al modificar el método de de Fraysseix et al., Brandenburg (2008) encontró una incrustación de cualquier grafo planar en un subconjunto triangular de la cuadrícula que consta de 4n² / ⁹ puntos. Un conjunto de puntos universal en forma de cuadrícula rectangular debe tener un tamaño de al menos n /3 × n /3 ^{[ 2 ]} , pero esto no excluye la posibilidad de conjuntos de puntos universales más pequeños de otros tipos. Los conjuntos de puntos universales más pequeños conocidos no se basan en cuadrículas, sino que se construyen a partir de superpatrones ( permutaciones que contienen todos los patrones de permutación de un tamaño dado); los conjuntos de puntos universales construidos de esta manera tienen un tamaño de ^n² / 4 − Θ ( n ). ^{[ 3 ]}                   

De Fraysseix, Pach y Pollack (1988) demostraron la primera cota inferior no trivial sobre el tamaño de un conjunto de puntos universal, con una cota de la forma n  +  Ω(√ n ), y Chrobak y Karloff (1989) demostraron que los conjuntos de puntos universales deben contener al menos 1,098 n − o ( n ) puntos. Kurowski (2004) estableció una cota aún más fuerte de 1,235 n − o ( n ), ^{[ 4 ]} que fue mejorada posteriormente por Scheucher, Schrezenmaier y Steiner (2018) a 1,293 n − o ( n ).      

Cerrar la brecha entre los límites inferiores lineales conocidos y los límites superiores cuadráticos sigue siendo un problema abierto . ^{[ 5 ]}

Las subclases de los grafos planares pueden, en general, tener conjuntos universales más pequeños (conjuntos de puntos que permiten dibujar en línea recta todos los grafos de n vértices de la subclase) que la clase completa de grafos planares, y en muchos casos son posibles conjuntos de puntos universales de exactamente n puntos. Por ejemplo, es fácil ver que todo conjunto de n puntos en posición convexa (que forman los vértices de un polígono convexo ) es universal para los grafos exteriores planares de n vértices , y en particular para los árboles . Menos obvio es que todo conjunto de n puntos en posición general (sin tres puntos colineales ) sigue siendo universal para los grafos exteriores planares. ^{[ 6 ]}

Los grafos planares que se pueden particionar en ciclos anidados, los grafos 2-exteriores planares y los grafos planares de ancho de camino acotado tienen conjuntos de puntos universales de tamaño casi lineal. ^{[ 7 ]} Los 3-árboles planares tienen conjuntos de puntos universales de tamaño O ( n ^3/2 log n ); la misma cota también se aplica a los grafos serie-paralelo . ^{[ 8 ]}

Además de para el dibujo de gráficos de líneas rectas, se han estudiado conjuntos de puntos universales para otros estilos de dibujo; en muchos de estos casos, existen conjuntos de puntos universales con exactamente n puntos, basados ​​en una incrustación topológica de libro en la que los vértices se colocan a lo largo de una línea en el plano y las aristas se dibujan como curvas que cruzan esta línea como máximo una vez. Por ejemplo, todo conjunto de n puntos colineales es universal para un diagrama de arco en el que cada arista se representa como un semicírculo simple o una curva suave formada por dos semicírculos. ^{[ 9 ]}

Mediante un diseño similar, se puede demostrar que toda curva estrictamente convexa en el plano contiene un subconjunto de n puntos que es universal para el dibujo de polilíneas con como máximo una curvatura por arista . ^{[ 10 ]} Este conjunto contiene solo los vértices del dibujo, no las curvaturas; se conocen conjuntos más grandes que se pueden usar para dibujar polilíneas con todos los vértices y todas las curvaturas dentro del conjunto. ^{[ 11 ]}