Incrustaciones convexas

En la teoría geométrica de grafos , una incrustación convexa de un grafo es una incrustación del grafo en un espacio euclidiano , con sus vértices representados como puntos y sus aristas como segmentos de línea , de modo que todos los vértices fuera de un subconjunto especificado pertenecen a la envoltura convexa de sus vecinos. Más precisamente, si${\displaystyle X}$es un subconjunto de los vértices del grafo, entonces una convexa${\displaystyle X}$-la incrustación incrusta el gráfico de tal manera que cada vértice pertenece a${\displaystyle X}$o se coloca dentro de la envoltura convexa de sus vecinos. Una incrustación convexa en${\displaystyle d}$Se dice que un espacio euclidiano de dimensión está en posición general si cada subconjunto${\displaystyle S}$de sus vértices abarca un subespacio de dimensión${\displaystyle \min(d,|S|-1)}$. ^{[ 1 ]}

Las incrustaciones convexas fueron introducidas por WT Tutte en 1963. Tutte demostró que si la cara exterior${\displaystyle F}$de un grafo planar se fija a la forma de un polígono convexo dado en el plano, y los vértices restantes se colocan resolviendo un sistema de ecuaciones lineales que describen el comportamiento de resortes ideales en los bordes del grafo, entonces el resultado será un polígono convexo.${\displaystyle F}$-incrustación. Más concretamente, cada cara de una incrustación construida de esta manera será un polígono convexo, lo que dará como resultado un dibujo convexo del grafo. ^{[ 2 ]}

Más allá de la planaridad, las incrustaciones convexas ganaron interés a partir de un resultado de 1988 de Nati Linial , László Lovász y Avi Wigderson que establece que un grafo es k -conexo por vértices si y solo si tiene un${\displaystyle (k-1)}$convexo de -dimensiones${\displaystyle S}$-incrustación en posición general, para algunos${\displaystyle S}$de${\displaystyle k}$de sus vértices, y que si es k -conexo por vértices, entonces tal incrustación puede construirse en tiempo polinomial eligiendo${\displaystyle S}$ser cualquier subconjunto de${\displaystyle k}$vértices y resolviendo el sistema de ecuaciones lineales de Tutte. ^{[ 1 ]}

Las incrustaciones convexas unidimensionales (en posición general), para un conjunto especificado de dos vértices, son equivalentes a las orientaciones bipolares del grafo dado. ^{[ 1 ]}