Dibujo convexo

Dibujos de cuadrícula convexos y estrictamente convexos del mismo gráfico

En el dibujo de un gráfico , un dibujo convexo de un gráfico plano es un dibujo que representa los vértices del gráfico como puntos en el plano euclidiano y las aristas como segmentos de línea recta, de tal manera que todas las caras del dibujo (incluida la cara exterior) tienen un límite convexo. El límite de una cara puede atravesar directamente uno de los vértices del gráfico sin girar; un dibujo estrictamente convexo pide además que el límite de la cara gire en cada vértice. Es decir, en un dibujo estrictamente convexo, cada vértice del gráfico es también un vértice de cada polígono convexo que describe la forma de cada cara incidente.

Cada gráfico poliédrico tiene un dibujo estrictamente convexo, ^[1] por ejemplo, obtenido como el diagrama de Schlegel de un poliedro convexo que representa el gráfico. Para estos gráficos, se puede encontrar un dibujo convexo (pero no necesariamente estrictamente convexo) dentro de una cuadrícula cuya longitud en cada lado es lineal en el número de vértices del gráfico, en tiempo lineal. ^{[2] [3]} Sin embargo, los dibujos estrictamente convexos pueden requerir cuadrículas más grandes; por ejemplo, para cualquier poliedro como una pirámide en la que una cara tiene un número lineal de vértices, un dibujo estrictamente convexo de su gráfico requiere una cuadrícula de área cúbica. ^[4]Un algoritmo de tiempo lineal puede encontrar dibujos estrictamente convexos de gráficos poliédricos en una cuadrícula cuya longitud en cada lado es cuadrática. ^[5]

Dibujo convexo pero no estrictamente convexo del gráfico bipartito completo ${\displaystyle K_{2,3}}$

Otros gráficos que no son poliédricos también pueden tener dibujos convexos, o dibujos estrictamente convexos. Algunos gráficos, como el gráfico bipartito completo , tienen dibujos convexos, pero no dibujos estrictamente convexos. Se conoce una caracterización combinatoria para los gráficos con dibujos convexos, ^[6] y se pueden reconocer en tiempo lineal, ^[7] pero las dimensiones de la cuadrícula necesarias para sus dibujos y un algoritmo eficiente para construir pequeños dibujos de cuadrículas convexas de estos gráficos no lo son. conocido en todos los casos. ^[8]${\displaystyle K_{2,3}}$

Los dibujos convexos deben distinguirse de las incrustaciones convexas , en las que se requiere que cada vértice se encuentre dentro del casco convexo de sus vértices vecinos. Las incrustaciones convexas pueden existir en dimensiones distintas a dos, no requieren que su gráfico sea plano, e incluso para las incrustaciones planas de gráficos planos no necesariamente obligan a la cara exterior a ser convexa. ^[9]

Referencias

1. Tutte, WT (1960), "Representaciones convexas de gráficos", Actas de la Sociedad Matemática de Londres , Tercera serie, 10 : 304–320, doi : 10.1112 / plms / s3-10.1.304 , MR  0114774
2. Kant, G. (1996), "Dibujar gráficas planas usando el orden canónico", Algorithmica , 16 (1): 4-32, doi : 10.1007 / s004539900035 , hdl : 1874/16676 , MR 1394492 
3. Bonichon, Nicolas; Felsner, Stefan; Mosbah, Mohamed (2007), "Dibujos convexos de gráficos planos de 3 conectados", Algorithmica , 47 (4): 399–420, doi : 10.1007 / s00453-006-0177-6 , MR 2304987 , S2CID 375595  
4. Andrews, George E. (1963), "Un límite inferior para el volumen de cuerpos estrictamente convexos con muchos puntos de celosía límite", Transactions of the American Mathematical Society , 106 (2): 270-279, doi : 10.2307 / 1993769 , JSTOR 1993769 , MR 0143105  
5. Bárány, Imre ; Rote, Günter (2006), "Dibujos estrictamente convexos de gráficos planos", Documenta Mathematica , 11 : 369–391, arXiv : cs / 0507030 , MR 2262937 
6. Thomassen, Carsten (1980), "Planaridad y dualidad de gráficos finitos e infinitos", Journal of Combinatorial Theory , Serie B, 29 (2): 244-271, doi : 10.1016 / 0095-8956 (80) 90083-0 , Señor 0586436 
7. Chiba, Norishige; Yamanouchi, Tadashi; Nishizeki, Takao (1984), "Algoritmos lineales para dibujos convexos de gráficos planos", en Bondy, J. Adrian; Murty, USR (eds.), Progreso en la teoría de grafos (Waterloo, Ontario, 1982) , Academic Press, págs. 153-173, MR 0776799 
8. Zhou, Xiao; Nishizeki, Takao (2010), "Dibujos convexos de gráficos planos triconectados internamente en cuadrículas", Matemáticas discretas, algoritmos y aplicaciones , 2 (3): 347–362, doi : 10.1142 / S179383091000070X , MR 2728831${\displaystyle O(n^{2})}$ 
9. Linial, N .; Lovász, L .; Wigderson, A. (1988), "Gomas elásticas, incrustaciones convexas y conectividad gráfica", Combinatorica , 8 (1): 91–102, doi : 10.1007 / BF02122557 , MR 0951998 , S2CID 6164458