En matemáticas combinatorias , una red apolínea es un gráfico no dirigido formado por un proceso de subdivisión recursiva de un triángulo en tres triángulos más pequeños. Redes de Apollonian pueden equivalentemente ser definidos como los planos 3-árboles , la máxima planar cordal gráficos, los singularmente 4-colorables grafos planos, y los gráficos de las politopos apilados . Llevan el nombre de Apolonio de Perge , quien estudió una construcción de empaquetadura de círculo relacionada.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/80/Apollonian-network.svg/240px-Apollonian-network.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/9/96/Goldner-Harary_graph.svg/220px-Goldner-Harary_graph.svg.png)
Definición
Se puede formar una red apolínea, comenzando desde un único triángulo incrustado en el plano euclidiano , seleccionando repetidamente una cara triangular de la incrustación, agregando un nuevo vértice dentro de la cara y conectando el nuevo vértice a cada vértice de la cara que lo contiene. De esta forma, el triángulo que contiene el nuevo vértice se subdivide en tres triángulos más pequeños, que a su vez pueden subdividirse de la misma forma.
Ejemplos de
Los gráficos completos en tres y cuatro vértices, K 3 y K 4 , son redes apolíneas. K 3 se forma comenzando con un triángulo y sin realizar ninguna subdivisión, mientras que K 4 se forma haciendo una sola subdivisión antes de detenerse.
El gráfico de Goldner-Harary es una red apolínea que forma el gráfico plano máximo no hamiltoniano más pequeño . [1] Nishizeki (1980) utilizó otra red apolínea más complicada para proporcionar un ejemplo de un gráfico plano máximo no hamiltoniano de 1 resistencia .
Caracterizaciones teóricas de grafos
Además de estar definidas por la subdivisión recursiva de triángulos, las redes apolíneas tienen varias otras caracterizaciones matemáticas equivalentes. Son los gráficos planos cordales máximos, los gráficos poliédricos cordales y los 3 árboles planos . Son los gráficos planos de 4 colores únicos y los gráficos planos con una descomposición única de la madera de Schnyder en tres árboles. Son los gráficos planos máximos con un ancho de árbol tres, una clase de gráficos que pueden caracterizarse por sus menores prohibidos o por su reducibilidad bajo transformaciones Y-Δ . Son los gráficos planos máximos con degeneración tres. También son los gráficos planos en un número dado de vértices que tienen el mayor número posible de triángulos, el mayor número posible de subgrafos tetraédricos, el mayor número posible de camarillas y el mayor número posible de piezas después de descomponerse separando triángulos.
Cordalidad
Las redes apolíneas son ejemplos de gráficos planos máximos , gráficos a los que no se pueden agregar bordes adicionales sin destruir la planaridad o, de manera equivalente, gráficos que se pueden dibujar en el plano de modo que cada cara (incluida la cara exterior) sea un triángulo. También son gráficos cordales , gráficos en los que cada ciclo de cuatro o más vértices tiene un borde diagonal que conecta dos vértices de ciclo no consecutivos, y el orden en el que se agregan los vértices en el proceso de subdivisión que forma una red apolínea es un orden de eliminación como un gráfico de cuerdas. Esto forma una caracterización alternativa de las redes apolíneas: son exactamente las gráficas planas máximas cordales o, de manera equivalente, las gráficas poliédricas cordales . [2]
En una red apolínea, cada camarilla máxima es un gráfico completo en cuatro vértices, formado al elegir cualquier vértice y sus tres vecinos anteriores. Cada separador de camarilla mínima (una camarilla que divide el gráfico en dos subgrafos desconectados) es uno de los triángulos subdivididos. Un gráfico cordal en el que todas las camarillas máximas y todos los separadores de camarillas mínimas tienen el mismo tamaño es un árbol k , y las redes apolíneas son ejemplos de 3 árboles. No todos los 3 árboles son planos, pero los 3 árboles planos son exactamente las redes apolíneas.
Colorabilidad única
Cada red de Apolínea es también un gráfico de 4 colores únicos . Debido a que es un gráfico plano, el teorema de los cuatro colores implica que tiene un color de gráfico con solo cuatro colores, pero una vez que se seleccionan los tres colores del triángulo inicial, solo hay una opción posible para el color de cada vértice sucesivo, por lo que hasta la permutación del conjunto de colores, tiene exactamente un color de 4. Es más difícil de probar, pero también cierto, que cada grafo plano de 4 colores únicos es una red apolínea. Por lo tanto, las redes apolíneas también se pueden caracterizar como las gráficas planas de 4 colores únicamente. [3] Las redes apolíneas también proporcionan ejemplos de gráficos planos que tienen el menor número posible de k- colores para k > 4 . [4]
Las redes apolíneas son también exactamente los gráficos planos máximos que (una vez que se fija una cara exterior) tienen una madera de Schnyder única , una partición de los bordes del gráfico en tres árboles intercalados enraizados en los tres vértices de la cara exterior. [5]
Ancho de árbol
Las redes apolíneas no forman una familia de grafos que se cierre bajo la operación de tomar grafos menores , ya que quitar aristas pero no vértices de una red apolínea produce un grafo que no es una red apolínea. Sin embargo, los 3 árboles parciales planos , subgráficos de las redes apolíneas, son menores cerrados. Por tanto, según el teorema de Robertson-Seymour , pueden caracterizarse por un número finito de menores prohibidos . Los menores mínimos prohibidos para los 3 árboles parciales planos son los cuatro gráficos mínimos entre los menores prohibidos para los gráficos planos y los 3 árboles parciales: el gráfico completo K 5 , el gráfico bipartito completo K 3,3 , el gráfico del octaedro , y la gráfica del prisma pentagonal . Las gráficas apolíneas son las gráficas máximas que no tienen ninguna de estas cuatro gráficas como menor. [6]
Una transformada Y-Δ , una operación que reemplaza un vértice de grado tres en un gráfico por un triángulo que conecta a sus vecinos, es suficiente (junto con la eliminación de los bordes paralelos) para reducir cualquier red apolínea a un solo triángulo, y más generalmente el Los gráficos planos que se pueden reducir a un solo borde mediante transformadas Y-Δ, eliminación de bordes paralelos, eliminación de vértices de grado uno y compresión de vértices de grado dos son exactamente los 3 árboles parciales planos. Los gráficos duales de los 3 árboles parciales planos forman otra familia de gráficos cerrados menores y son exactamente los gráficos planos que se pueden reducir a un solo borde mediante transformaciones Δ-Y, eliminación de bordes paralelos, eliminación de vértices de grado uno y compresión de vértices de grado dos. [7]
Degeneración
En cada subgrafo de una red apolínea, el vértice agregado más recientemente tiene un grado como máximo tres, por lo que las redes apolíneas tienen una degeneración tres. El orden en el que se agregan los vértices para crear la red es, por lo tanto, un orden de degeneración, y las redes apolíneas coinciden con los gráficos planos máximos de 3 degenerados.
Extremalidad
Otra caracterización de las redes apolíneas tiene que ver con su conectividad . Cualquier gráfico plano máximo puede descomponerse en subgráficos planos máximos conectados a 4 vértices dividiéndolo a lo largo de sus triángulos de separación (triángulos que no son caras del gráfico): dado cualquier triángulo no facial: uno puede formar dos gráficos planos máximos más pequeños, uno que consta de la parte dentro del triángulo y el otro que consta de la parte fuera del triángulo. Los gráficos planos máximos sin triángulos separados que pueden formarse mediante divisiones repetidas de este tipo a veces se denominan bloques, aunque ese nombre también se ha utilizado para los componentes biconectados de un gráfico que no está biconectado en sí mismo. Una red apolínea es un gráfico plano máximo en el que todos los bloques son isomorfos al gráfico completo K 4 .
En la teoría de grafos extremos , las redes apolíneas son también exactamente los gráficos planos de n -vértices en los que el número de bloques alcanza su máximo, n - 3 , y los gráficos planos en los que el número de triángulos alcanza su máximo, 3 n - 8 . Dado que cada subgrafo K 4 de un grafo plano debe ser un bloque, estos tambien son los grafos planos en los que el numero de subgrafos K 4 alcanza su maximo, n - 3 , y los grafos en los que el numero de camarillas de cualquier tipo alcanza su máximo, 8 n - 16 . [8]
Realizaciones geométricas
Construcción a partir de empaquetaduras circulares
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/e6/Apollonian_gasket.svg/220px-Apollonian_gasket.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/a0/Circle_packing_theorem_K5_minus_edge_example.svg/220px-Circle_packing_theorem_K5_minus_edge_example.svg.png)
Las redes apolíneas llevan el nombre de Apolonio de Perge , quien estudió el problema de Apolonio de construir un círculo tangente a otros tres círculos. Un método para construir redes apolíneas es comenzar con tres círculos mutuamente tangentes y luego inscribir repetidamente otro círculo dentro del espacio formado por tres círculos previamente dibujados. La colección fractal de círculos producidos de esta manera se llama junta apolínea .
Si el proceso de producir una junta apolínea se detiene antes, con solo un conjunto finito de círculos, entonces el gráfico que tiene un vértice para cada círculo y un borde para cada par de círculos tangentes es una red apolínea. [9] La existencia de un conjunto de círculos tangentes cuyas tangencias representan una red apolínea dada forma una instancia simple del teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston , que establece que cualquier grafo plano se puede representar mediante círculos tangentes de la misma manera . [10]
Poliedros
Las redes apolíneas son gráficos planos conectados en 3 y, por lo tanto, según el teorema de Steinitz , siempre se pueden representar como los gráficos de poliedros convexos . El poliedro convexo que representa una red apolínea es un politopo apilado tridimensional . Dicho politopo se puede obtener a partir de un tetraedro pegando repetidamente tetraedros adicionales uno a la vez en sus caras triangulares. Por lo tanto, las redes apolíneas también se pueden definir como los gráficos de politopos 3d apilados. [11] Es posible encontrar una representación de cualquier red apolínea como poliedro convexo 3d en el que todas las coordenadas son números enteros de tamaño polinomial, mejor que lo que se conoce para otras gráficas planas. [12]
Mallas triangulares
La subdivisión recursiva de triángulos en tres triángulos más pequeños fue investigada como una técnica de segmentación de imágenes en visión por computadora por Elcock, Gargantini y Walsh (1987) ; en este contexto, lo llamaron la descomposición ternaria del triángulo escaleno . Observaron que, al colocar cada nuevo vértice en el centroide de su triángulo circundante, la triangulación podría elegirse de tal manera que todos los triángulos tengan áreas iguales, aunque no todos tengan la misma forma. De manera más general, las redes apolíneas pueden dibujarse en el plano con cualquier área prescrita en cada cara; si las áreas son números racionales , también lo son todas las coordenadas de los vértices. [13]
También es posible realizar el proceso de subdividir un triángulo para formar una red apolínea de tal manera que, en cada paso, las longitudes de los bordes sean números racionales; es un problema abierto si cada grafo plano tiene un dibujo con esta propiedad. [14] Es posible en tiempo polinomial encontrar un dibujo de un árbol tridimensional plano con coordenadas enteras minimizando el área del cuadro delimitador del dibujo, y probar si un árbol tridimensional plano dado se puede dibujar con sus vértices en un conjunto dado de puntos. [15]
Propiedades y aplicaciones
Gráficos sin coincidencias
Plummer (1992) utilizó redes apolíneas para construir una familia infinita de gráficos planos máximos con un número par de vértices pero sin una correspondencia perfecta . Los gráficos de Plummer se forman en dos etapas. En la primera etapa, a partir de un triángulo abc , se subdivide repetidamente la cara triangular de la subdivisión que contiene la arista bc : el resultado es un gráfico que consta de una ruta desde a hasta el vértice de subdivisión final junto con una arista de cada vértice de la ruta a cada uno de b y c . En la segunda etapa, cada una de las caras triangulares del gráfico plano resultante se subdivide una vez más. Si la ruta desde a hasta el vértice de subdivisión final de la primera etapa tiene una longitud uniforme, entonces el número de vértices en el gráfico general también es par. Sin embargo, aproximadamente 2/3 de los vértices son los que se insertan en la segunda etapa; estos forman un conjunto independiente y no se pueden emparejar entre sí, ni hay suficientes vértices fuera del conjunto independiente para encontrar coincidencias para todos ellos.
Aunque las redes apolíneas en sí mismas pueden no tener coincidencias perfectas, las gráficas duales planas de las redes apolíneas son gráficas regulares tridimensionales sin bordes cortados , por lo que, según un teorema de Petersen (1891) , se garantiza que tienen al menos una coincidencia perfecta. Sin embargo, en este caso se sabe más: los duales de las redes apolíneas siempre tienen un número exponencial de emparejamientos perfectos. [16] László Lovász y Michael D. Plummer conjeturaron que un límite inferior exponencial similar se cumple de manera más general para cada gráfico de 3 regulares sin bordes cortados, un resultado que se probó más tarde.
Gráficos de ley de potencia
Andrade y col. (2005) estudiaron leyes de potencia en las secuencias de grados de un caso especial de redes de este tipo, formadas al subdividir todos los triángulos el mismo número de veces. Utilizaron estas redes para modelar empaquetamientos de espacio por partículas de diferentes tamaños. Con base en su trabajo, otros autores introdujeron redes apolíneas aleatorias, formadas eligiendo repetidamente una cara aleatoria para subdividir, y demostraron que estas también obedecen las leyes de potencia en su distribución de grados [17] y tienen distancias medias pequeñas. [18] Alan M. Frieze y Charalampos E. Tsourakakis analizaron los grados más altos y los valores propios de las redes apolíneas aleatorias. [19] Andrade y col. También observó que sus redes satisfacen el efecto de mundo pequeño , que todos los vértices están a una pequeña distancia entre sí. Con base en evidencia numérica, estimaron que la distancia promedio entre pares de vértices seleccionados al azar en una red de n- vértices de este tipo era proporcional a (log n ) 3/4 , pero investigadores posteriores demostraron que la distancia promedio es en realidad proporcional a log n . [20]
Distribución de ángulos
Butler y Graham (2010) observaron que si cada nuevo vértice se coloca en el incentro de su triángulo, de modo que las aristas del nuevo vértice bisecan los ángulos del triángulo, entonces el conjunto de triples de ángulos de triángulos en la subdivisión, cuando reinterpretado como triples de coordenadas baricéntricas de puntos en un triángulo equilátero , converge en forma al triángulo de Sierpinski a medida que aumenta el número de niveles de subdivisión.
Hamiltonicidad
Takeo (1960) afirmó erróneamente que todas las redes apolíneas tienen ciclos hamiltonianos ; sin embargo, el gráfico de Goldner-Harary proporciona un contraejemplo. Si una red apolínea tiene una dureza mayor que uno (lo que significa que eliminar cualquier conjunto de vértices del gráfico deja un número menor de componentes conectados que el número de vértices eliminados) entonces necesariamente tiene un ciclo hamiltoniano, pero existen redes apolíneas no hamiltonianas cuya dureza es igual a uno. [21]
Enumeración
La enumeración combinatoria problema de contar triangulaciones Apollonian fue estudiada por Takeo (1960) , que demostraron que tienen la sencilla función de generación de f ( x ) descrita por la ecuación f ( x ) = 1 + x ( f ( x )) 3 . En esta función generadora, el término de grado n cuenta el número de redes apolíneas con un triángulo exterior fijo y n + 3 vértices. Por lo tanto, los números de redes apolíneas (con un triángulo exterior fijo) en 3, 4, 5, ... vértices son:
- 1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (secuencia A001764 en la OEIS ),
una secuencia que también cuenta árboles ternarios y disecciones de polígonos convexos en polígonos de lados impares. Por ejemplo, hay 12 redes apolíneas de 6 vértices: tres formadas subdividiendo el triángulo exterior una vez y luego subdividiendo dos de los triángulos resultantes, y nueve formadas subdividiendo el triángulo exterior una vez, subdividiendo uno de sus triángulos y luego subdividiendo uno de los siguientes. los triángulos más pequeños resultantes.
Historia
Birkhoff (1930) es uno de los primeros trabajos que utiliza una forma dual de redes apolíneas, los mapas planos formados al colocar repetidamente nuevas regiones en los vértices de mapas más simples, como una clase de ejemplos de mapas planos con pocos colores.
Las estructuras geométricas estrechamente relacionadas con las redes apolíneas se han estudiado en combinatoria poliédrica desde al menos principios de la década de 1960, cuando fueron utilizadas por Grünbaum (1963) para describir gráficos que se pueden realizar como el gráfico de un politopo de una sola forma, sin dimensiones ni ambigüedades combinatorias, y por Moon & Moser (1963) para encontrar politopos simpliciales sin caminos largos. En la teoría de grafos , la estrecha conexión entre planaridad y ancho de árbol se remonta a Robertson y Seymour (1984) , quienes demostraron que cada familia de grafos cerrados menores tiene un ancho de árbol acotado o contiene todos los gráficos planos. Hakimi y Schmeichel (1979) , Alon y Caro (1984) , Patil (1986) y muchos autores desde entonces consideraron explícitamente los árboles planos 3, como una clase de gráficos .
El nombre de "red apolínea" fue dado por Andrade et al. (2005) a las redes que estudiaron en las que el nivel de subdivisión de triángulos es uniforme en toda la red; estas redes corresponden geométricamente a un tipo de poliedro apilado llamado Kleetope . [22] Otros autores aplicaron el mismo nombre de manera más amplia a los árboles 3 planos en su trabajo generalizando el modelo de Andrade et al. a redes apolíneas aleatorias. [18] Las triangulaciones generadas de esta manera también se han denominado "triangulaciones apiladas" [23] o " triangulaciones apiladas ". [24]
Ver también
- Subdivisión baricéntrica , un método diferente para subdividir triángulos en triángulos más pequeños
- Superficie de subdivisión de bucle , otro método más para subdividir triángulos en triángulos más pequeños
Notas
- ^ Este gráfico lleva el nombre del trabajo de Goldner y Harary (1975) ; sin embargo, aparece antes en la literatura, por ejemplo en Grünbaum (1967) , p. 357.
- ↑ Patil (1986) estableció sin pruebas la equivalencia de los 3 árboles planos y los gráficos planos acordes máximos. Para obtener una prueba, consulte Markenzon, Justel & Paciornik (2006) . Para una caracterización más general de los gráficos planos acordes y un algoritmo de reconocimiento eficiente para estos gráficos, consulte Kumar y Madhavan (1989) . La observación de que cada grafo poliédrico cordal es plano máximo fue establecido explícitamente por Gerlach (2004) .
- ^ Fowler (1998) .
- ↑ El hecho de que las redes apolíneas minimicen el número de coloraciones con más de cuatro colores fue mostrado en una forma dual para coloraciones de mapas por Birkhoff (1930) .
- ^ Felsner y Zickfeld (2008) ; Bernardi y Bonichon (2009) .
- ↑ Los dos menores prohibidos para gráficas planas vienen dados por el teorema de Wagner . Para los menores prohibidos para 3 árboles parciales (que incluyen también el gráfico de Wagner no plano ), ver Arnborg, Proskurowski & Corniel (1986) y Bodlaender (1998) . Para obtener pruebas directas de que el gráfico octaédrico y el gráfico de prisma pentagonal son los únicos dos menores prohibidos planos, consulte Dai y Sato (1990) y El-Mallah y Colbourn (1990) .
- ↑ Politof (1983) introdujo las gráficas planas reducibles Δ-Y y las caracterizó en términos de subgrafos homeomórficos prohibidos. La dualidad entre los gráficos reducibles Δ-Y e Y-Δ, las caracterizaciones menores prohibidas de ambas clases y la conexión con los árboles 3 parciales planos son todos de El-Mallah y Colbourn (1990) .
- ^ Para la caracterización en términos del número máximo de triángulos en un gráfico plano, consulte Hakimi y Schmeichel (1979) . Alon y Caro (1984) citan este resultado y proporcionan las caracterizaciones en términos de las clases de isomorfismos de bloques y números de bloques. El límite del número total de camarillas se sigue fácilmente de los límites de los triángulos y lossubgráficos K 4 , y también lo establece de forma explícita Wood (2007) , que proporciona una red apolínea como ejemplo que muestra que este límite es estrecho. Para generalizaciones de estos límites a superficies no planas, consulte Dujmović et al. (2009) .
- ^ Andrade y col. (2005) .
- ^ Thurston (1978-1981) .
- ^ Véase, por ejemplo, abajo, De Loera & Richter-Gebert (2000) .
- ^ Demaine y Schulz (2011) .
- ^ Biedl y Ruiz Velázquez (2010) .
- ^ Para subdividir un triángulo con longitudes racionales de los lados de modo que los triángulos más pequeños también tengan longitudes racionales de los lados, véase Almering (1963) . Para conocer el progreso en el problema general de encontrar dibujos planos con longitudes de borde racionales, consulte Geelen, Guo & McKinnon (2008) .
- ^ Para los dibujos con coordenadas enteras, consulte Mondal et al. (2010) , y para los dibujos en un conjunto de vértices dado, ver Nishat, Mondal & Rahman (2011) .
- ^ Jiménez y Kiwi (2010) .
- ↑ Tsourakakis (2011)
- ^ a b Zhou y col. (2004) ; Zhou, Yan y Wang (2005) .
- ^ Frieze y Tsourakakis (2011)
- ^ Albenque y Marckert (2008) ; Zhang y col. (2008) .
- ^ Ver Nishizeki (1980) para un ejemplo no hamiltoniano de 1 duro, Böhme, Harant & Tkáč (1999) para la prueba de que las redes apolíneas con mayor dureza son hamiltonianas, y Gerlach (2004) para una extensión de este resultado a un clase de gráficos planos.
- ^ Grünbaum (1963) ; Grünbaum (1967) .
- ^ Alon y Caro (1984) ; Zickfeld y Ziegler (2006) ; Badent y col. (2007) ; Felsner y Zickfeld (2008) .
- ^ Albenque y Marckert (2008) ; Bernardi y Bonichon (2009) ; Jiménez y Kiwi (2010) .
Referencias
- Albenque, Marie; Marckert, Jean-François (2008), "Algunas familias de mapas planos crecientes" , Electronic Journal of Probability , 13 : 1624–1671, arXiv : 0712.0593 , doi : 10.1214 / ejp.v13-563 , MR 2438817 , S2CID 2420262
- Almering, JHJ (1963), "Cuadriláteros racionales", Indagationes Mathematicae , 25 : 192-199, doi : 10.1016 / S1385-7258 (63) 50020-1 , MR 0147447.
- Alon, N .; Caro, Y. (1984), "Sobre el número de subgrafos de tipo prescrito de grafos planos con un número dado de vértices", en Rosenfeld, M .; Zaks, J. (eds.), Convexity and Graph Theory: actas de la Conferencia sobre Convexity and Graph Theory, Israel, marzo de 1981 , Annals of Discrete Mathematics 20, North-Holland Mathematical Studies 87, Elsevier, págs. 25-36, ISBN 978-0-444-86571-7, MR 0791009.
- Andrade, José S., Jr .; Herrmann, Hans J .; Andrade, Roberto FS; da Silva, Luciano R. (2005), "Redes apolíneas: simultáneamente sin escala, mundo pequeño, euclidiano, relleno de espacio y con gráficos coincidentes", Physical Review Letters , 94 (1): 018702, arXiv : cond-mat / 0406295 , código bibliográfico : 2005PhRvL..94a8702A , doi : 10.1103 / physrevlett.94.018702 , PMID 15698147.
- Arnborg, S .; Proskurowski, A .; Corniel, D. (1986), Caracterización de menores prohibidos de 3 árboles parciales , Informe técnico CIS-TR-86-07, Departamento de Ciencias de la Información y la Computación, Universidad de Oregon. Según lo citado por El-Mallah y Colbourn (1990) .
- Badent, Melanie; Binucci, Carla; Di Giacomo, Emilio; Didimo, Walter; Felsner, Stefan; Giordano, Francesco; Kratochvíl, Jan; Palladino, Pietro; Patrignani, Maurizio; Trotta, Francesco (2007), "Representaciones de contacto de triángulos homotéticos de gráficos planos", Conferencia Canadiense sobre Geometría Computacional (PDF).
- Abajo, Alejandro; De Loera, Jesús A .; Richter-Gebert, Jürgen (2000), La complejidad de encontrar pequeñas triangulaciones de 3 politopos convexos , arXiv : math / 0012177 , Bibcode : 2000math ..... 12177B.
- Bernardi, Olivier; Bonichon, Nicolas (2009), "Intervalos en celosías catalanas y realizadores de triangulaciones", Revista de teoría combinatoria , Serie A, 116 (1): 55–75, doi : 10.1016 / j.jcta.2008.05.005 , MR 2469248.
- Biedl, Therese ; Ruiz Velázquez, Lesvia Elena (2010), "Dibujar 3 árboles planos con áreas de caras determinadas", Dibujo gráfico, 17º Simposio Internacional, GD 2009, Chicago, IL, EE. UU., 22 al 25 de septiembre de 2009, Artículos revisados , Notas de conferencias en Ciencias de la Computación, 5849 , Springer-Verlag, págs. 316–322, doi : 10.1007 / 978-3-642-11805-0_30.
- Birkhoff, George D. (1930), "Sobre el número de formas de colorear un mapa", Proceedings of the Edinburgh Mathematical Society , (2), 2 (2): 83–91, doi : 10.1017 / S0013091500007598.
- Bodlaender, Hans L. (1998), "Un k -arboreto parcial de gráficos con ancho de árbol acotado", Ciencias de la computación teóricas , 209 (1–2): 1–45, doi : 10.1016 / S0304-3975 (97) 00228-4 , HDL : 1874/18312 , MR 1647486.
- Böhme, Thomas; Harant, Jochen; Tkáč, Michal (1999), "Más de un gráfico plano de acordes difíciles son hamiltonianos", Journal of Graph Theory , 32 (4): 405–410, doi : 10.1002 / (SICI) 1097-0118 (199912) 32: 4 < 405 :: AID-JGT8> 3.3.CO; 2-Q , MR 1722793.
- Butler, S .; Graham, Ron (2010), "Particiones triangulares iteradas", en Katona, G .; Schrijver, A .; Szonyi, T. (eds.), Fiesta de Combinatoria y Ciencias de la Computación (PDF) , Estudios Matemáticos de la Sociedad Bolyai, 29 , Heidelberg: Springer-Verlag, págs. 23–42.
- Dai, Wayne Wei-Ming; Sato, Masao (1990), "Caracterización mínima mínima prohibida de 3 árboles parciales planos y aplicación al diseño de circuitos", Simposio internacional sobre circuitos y sistemas de IEEE , 4 , págs. 2677–2681, doi : 10.1109 / ISCAS.1990.112560 , S2CID 122926229
- Demaine, Erik ; Schulz, André (2011), "Incrustación de politopos apilados en una cuadrícula de tamaño polinomial", Proc. Simposio ACM-SIAM sobre algoritmos discretos (PDF) , págs. 1177–1187, archivado desde el original (PDF) en 2011-06-01 , consultado 2011-03-07.
- Dujmović, Vida; Fijavž, Gašper; Joret, Gwenaël; Wood, David R. (2009), "El número máximo de camarillas en un gráfico incrustado en una superficie", European Journal of Combinatorics , 32 (8): 1244-1252, arXiv : 0906.4142 , Bibcode : 2009arXiv0906.4142D , doi : 10.1016 / j.ejc.2011.04.001 , S2CID 1733300.
- El-Mallah, Ehab S .; Colbourn, Charles J. (1990), "Sobre dos clases duales de gráficos planos", Matemáticas discretas , 80 (1): 21–40, doi : 10.1016 / 0012-365X (90) 90293-Q , MR 1045921.
- Elcock, EW; Gargantini, I .; Walsh, TR (1987), "Descomposición triangular", Computación de imagen y visión , 5 (3): 225-231, doi : 10.1016 / 0262-8856 (87) 90053-9.
- Felsner, Stefan; Zickfeld, Florian (2008), "Sobre el número de orientaciones planas con grados prescritos" (PDF) , Electronic Journal of Combinatorics , 15 (1): R77, arXiv : math / 0701771 , Bibcode : 2007math ...... 1771F , doi : 10.37236 / 801 , MR 2.411.454 , S2CID 13893657.
- Frieze, Alan M .; Tsourakakis, Charalampos E. (2011), Vértices de alto grado, valores propios y diámetro de redes apolíneas aleatorias , arXiv : 1104.5259 , Bibcode : 2011arXiv1104.5259F.
- Fowler, Thomas (1998), Coloración única de gráficos planos (PDF) , Ph.D. tesis, Departamento de Matemáticas del Instituto de Tecnología de Georgia.
- Geelen, Jim; Guo, Anjie; McKinnon, David (2008), "Incrustaciones de líneas rectas de gráficas planas cúbicas con longitudes de aristas enteras", Journal of Graph Theory , 58 (3): 270-274, doi : 10.1002 / jgt.20304 , MR 2419522.
- Gerlach, T. (2004), "Toughness and Hamiltonicity of a class of planar graphs", Discrete Mathematics , 286 (1–2): 61–65, doi : 10.1016 / j.disc.2003.11.046 , MR 2084280.
- Goldner, A .; Harary, F. (1975), "Nota sobre un gráfico planar máximo no hamiltoniano más pequeño", Bull. Matemáticas de Malasia. Soc. , 6 (1): 41–42. Ver también la misma revista 6 (2): 33 (1975) y 8 : 104-106 (1977). Referencia de la lista de publicaciones de Harary .
- Grünbaum, Branko (1963), "Gráficos poliédricos no ambiguos", Israel Journal of Mathematics , 1 (4): 235-238, doi : 10.1007 / BF02759726 , MR 0185506 , S2CID 121075042.
- Grünbaum, Branko (1967), Politopos convexos , Wiley Interscience.
- Hakimi, SL ; Schmeichel, EF (1979), "Sobre el número de ciclos de longitud k en un gráfico plano máximo", Journal of Graph Theory , 3 (1): 69–86, doi : 10.1002 / jgt.3190030108 , MR 0519175.
- Jiménez, Andrea; Kiwi, Marcos (2010), Contar coincidencias perfectas de gráficas cúbicas en el dual geométrico , arXiv : 1010.5918 , Bibcode : 2010arXiv1010.5918J.
- Kumar, P. Sreenivasa; Madhavan, CE Veni (1989), "A new class of separators and planarity of chordal graphs", Foundations of Software Technology and Theoretical Computer Science, Novena Conferencia, Bangalore, India 19-21 de diciembre de 1989, Actas , Notas de conferencias en Ciencias de la Computación , 405 , Springer-Verlag, págs. 30–43, doi : 10.1007 / 3-540-52048-1_30 , MR 1048636.
- Markenzon, L .; Justel, CM; Paciornik, N. (2006), "Subclases de árboles k : caracterización y reconocimiento", Matemáticas aplicadas discretas , 154 (5): 818–825, doi : 10.1016 / j.dam.2005.05.021 , MR 2207565.
- Mondal, Debajyoti; Nishat, Rahnuma Islam; Rahman, Md. Saidur; Alam, Muhammad Jawaherul (2010), "Dibujos de área mínima de tres árboles planos", Conferencia Canadiense sobre Geometría Computacional (PDF).
- Luna, JW; Moser, L. (1963), "Sendas simples en poliedros" , Pacific Journal of Mathematics , 13 (2): 629–631, doi : 10.2140 / pjm.1963.13.629 , MR 0154276.
- Nishat, Rahnuma Islam; Mondal, Debajyoti; Rahman, Md. Saidur (2011), "Embeddings Point-set of Plane 3-trees", Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Springer-Verlag, págs. 317–328, doi : 10.1007 / 978-3-642-18469-7_29.
- Nishizeki, Takao (1980), "A 1-hard non-hamiltonian maximal planar graph", Discrete Mathematics , 30 (3): 305-307, doi : 10.1016 / 0012-365X (80) 90240-X , MR 0573648.
- Patil, HP (1986), "Sobre la estructura de los árboles k ", Journal of Combinatorics, Information and System Sciences , 11 (2-4): 57-64, MR 0966069.
- Petersen, Julius (1891), "Die Theorie der regulären graphs", Acta Mathematica , 15 : 193-220, doi : 10.1007 / BF02392606.
- Plummer, Michael D. (1992), "Ampliación de coincidencias en gráficas planas IV", Matemáticas discretas , 109 (1-3): 207-219, doi : 10.1016 / 0012-365X (92) 90292-N , MR 1192384.
- Politof, T. (1983), Caracterización y cálculo de confiabilidad eficiente de redes reducibles Δ-Y , Ph.D. tesis, Universidad de California, Berkeley. Según lo citado por El-Mallah y Colbourn (1990) .
- Robertson, Neil ; Seymour, PD (1984), "Graph minors. III. Planar tree-width", Journal of Combinatorial Theory , Serie B, 36 (1): 49-64, doi : 10.1016 / 0095-8956 (84) 90013-3 , Señor 0742386.
- Takeo, Fujio (1960), "Sobre grafos triangulados. I", Bull. Universidad de Fukuoka Gakugei III , 10 : 9-21, MR 0131372. El revisor de MathSciNet , WT Tutte, señaló un error con respecto a la hamiltonicidad .
- Thurston, William (1978-1981), La geometría y topología de tres variedades , notas de la conferencia de Princeton.
- Tsourakakis, Charalampos E. (2011), La secuencia de grados de redes apolíneas aleatorias , arXiv : 1106.1940.
- Wood, David R. (2007), "Sobre el número máximo de camarillas en un gráfico", Graphs and Combinatorics , 23 (3): 337–352, arXiv : math / 0602191 , doi : 10.1007 / s00373-007-0738- 8 , MR 2.320.588 , S2CID 46700417.
- Zhang, Zhongzhi; Chen, Lichao; Zhou, Shuigeng; Fang, Lujun; Guan, Jihong; Zou, Tao (2008), "Solución analítica de longitud de ruta promedio para redes apolíneas", Physical Review E , 77 (1): 017102, arXiv : 0706.3491 , Bibcode : 2008PhRvE..77a7102Z , doi : 10.1103 / PhysRevE.77.017102 , PMID 18351964 , S2CID 30404208.
- Zhou, Tao; Yan, Gang; Wang, Bing-Hong (2005), "Redes planas máximas con gran coeficiente de agrupamiento y distribución de grados de ley de potencia", Physical Review E , 71 (4): 046141, arXiv : cond-mat / 0412448 , Bibcode : 2005PhRvE..71d6141Z , doi : 10.1103 / PhysRevE.71.046141 , PMID 15903760 , S2CID 21740312.
- Zhou, Tao; Yan, Gang; Zhou, Pei-Ling; Fu, Zhong-Qian; Wang, Bing-Hong (2004), Redes apolíneas aleatorias , arXiv : cond-mat / 0409414v2 , Bibcode : 2004cond.mat..9414Z.
- Zickfeld, Florian; Ziegler, Günter M. (2006), "Realizaciones enteras de politopos apilados", Taller de combinatoria geométrica y topológica (PDF).
enlaces externos
- Weisstein, Eric W. "Red apolínea" . MathWorld .
- Código de simulación de Matlab