Hispanopedia Wiki
Articulo de referencia

red apolínea

Una red apolínea El grafo de Goldner-Harary , una red apolínea no hamiltoniana En matemáticas combinatorias , una red apolínea es un grafo no dirigido formado mediante la subdiv...

Hispanopedia WikiContenido en espanolLectura gratuita
Una red apolínea
El grafo de Goldner-Harary , una red apolínea no hamiltoniana

En matemáticas combinatorias , una red apolínea es un grafo no dirigido formado mediante la subdivisión recursiva de un triángulo en tres triángulos más pequeños. Las redes apolíneas también pueden definirse como 3-árboles planares , grafos cordales planares máximos, grafos planares con 4 colores únicos y grafos de politopos apilados . Reciben su nombre de Apolonio de Perga , quien estudió una construcción relacionada de empaquetamiento de círculos.

Definición

Se puede formar una red apolínea, partiendo de un único triángulo incrustado en el plano euclidiano , seleccionando repetidamente una cara triangular de la incrustación, añadiendo un nuevo vértice dentro de dicha cara y conectando el nuevo vértice con cada uno de los vértices 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 manera.

Ejemplos

Los grafos completos de tres y cuatro vértices, K 3 y K 4 , son ambos redes apolíneas. K 3 se forma partiendo de un triángulo sin realizar ninguna subdivisión, mientras que K 4 se forma realizando una única subdivisión antes de detenerse.

El grafo de Goldner-Harary es una red apolínea que forma el grafo planar maximal no hamiltoniano más pequeño . [ 1 ] Nishizeki (1980) utilizó otra red apolínea más compleja para proporcionar un ejemplo de un grafo planar maximal no hamiltoniano 1-resistente . [ 2 ]

Caracterizaciones basadas en la teoría 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 grafos planares maximales cordales , los grafos poliédricos cordales y los 3-árboles planares . Son los grafos planares 4-coloreables de forma única y los grafos planares con una descomposición de Schnyder wood única en tres árboles. Son los grafos planares maximales con ancho de árbol tres, una clase de grafos que pueden caracterizarse por sus menores prohibidos o por su reducibilidad bajo transformaciones Y-Δ . Son los grafos planares maximales con degeneración tres. También son los grafos planares 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 cliques y el mayor número posible de piezas después de descomponerlos separando triángulos.

Cordalidad

Las redes apolíneas son ejemplos de grafos planares máximos , grafos a los que no se pueden añadir aristas adicionales sin destruir la planaridad, o equivalentemente, grafos que se pueden dibujar en el plano de manera que cada cara (incluida la cara exterior) sea un triángulo. También son grafos cordales , grafos en los que cada ciclo de cuatro o más vértices tiene una arista diagonal que conecta dos vértices de ciclo no consecutivos, y el orden en que se añaden los vértices en el proceso de subdivisión que forma una red apolínea es un orden de eliminación como en un grafo cordal. Esto constituye una caracterización alternativa de las redes apolíneas: son exactamente los grafos planares máximos cordales o, equivalentemente, los grafos poliédricos cordales . [ 3 ]

En una red apolínea, cada camarilla máxima es un grafo completo de cuatro vértices, formado al elegir cualquier vértice y sus tres vecinos anteriores. Cada separador de camarilla mínimo (una camarilla que divide el grafo en dos subgrafos desconectados) es uno de los triángulos subdivididos. Un grafo cordal en el que todas las camarillas máximas y todos los separadores de camarilla mínimos tienen el mismo tamaño es un k -árbol , y las redes apolíneas son ejemplos de 3-árboles. No todos los 3-árboles son planares, pero los 3-árboles planares son precisamente las redes apolíneas.

Coloración única

Toda red apolínea es también un grafo con una única coloración de 4 colores . Debido a que es un grafo planar, el teorema de los cuatro colores implica que tiene una coloración de grafo con solo cuatro colores, pero una vez seleccionados los tres colores del triángulo inicial, solo hay una opción posible para el color de cada vértice sucesivo, por lo que, salvo permutación del conjunto de colores, tiene exactamente una coloración de 4 colores. Es más difícil de demostrar, pero también cierto, que todo grafo planar con una única coloración de 4 colores es una red apolínea. Por lo tanto, las redes apolíneas también pueden caracterizarse como los grafos planares con una única coloración de 4 colores. [ 4 ] Las redes apolíneas también proporcionan ejemplos de grafos planares que tienen la menor cantidad posible de k -coloraciones para k > 4. [ 5 ]

Las redes apolíneas son también exactamente los grafos planares máximos que (una vez fijada una cara exterior) tienen un único bosque de Schnyder , una partición de las aristas del grafo en tres árboles entrelazados enraizados en los tres vértices de la cara exterior. [ 6 ]

Ancho del árbol

Las redes apolíneas no forman una familia de grafos cerrada bajo la operación de tomar menores de grafos , ya que al eliminar aristas pero no vértices de una red apolínea se obtiene un grafo que no es una red apolínea. Sin embargo, los 3-árboles parciales planares , subgrafos de las redes apolíneas, son cerrados bajo menores. Por lo tanto, según el teorema de Robertson-Seymour , se pueden caracterizar por un número finito de menores prohibidos . Los menores prohibidos mínimos para los 3-árboles parciales planares son los cuatro grafos mínimos entre los menores prohibidos para los grafos planares y los 3-árboles parciales: el grafo completo K 5 , el grafo bipartito completo K 3,3 , el grafo del octaedro y el grafo del prisma pentagonal . Los grafos apolíneas son los grafos maximales que no tienen ninguno de estos cuatro grafos como menor. [ 7 ]

Una transformación Y-Δ , una operación que reemplaza un vértice de grado tres en un grafo por un triángulo que conecta sus vecinos, es suficiente (junto con la eliminación de aristas paralelas) para reducir cualquier red apolínea a un solo triángulo, y más generalmente los grafos planares que pueden reducirse a una sola arista mediante transformaciones Y-Δ, eliminación de aristas paralelas, eliminación de vértices de grado uno y compresión de vértices de grado dos son precisamente los 3-árboles parciales planares. Los grafos duales de los 3-árboles parciales planares forman otra familia de grafos cerrados en menores y son precisamente los grafos planares que pueden reducirse a una sola arista mediante transformaciones Δ-Y, eliminación de aristas paralelas, eliminación de vértices de grado uno y compresión de vértices de grado dos. [ 8 ]

Degeneración

En cada subgrafo de una red apolínea, el vértice añadido más recientemente tiene un grado máximo de tres, por lo que las redes apolíneas tienen degeneración tres. El orden en que se añaden los vértices para crear la red constituye, por lo tanto, un orden de degeneración, y las redes apolíneas coinciden con los grafos planares máximos degenerados en grado tres.

Extremidad

Otra caracterización de las redes apolíneas implica su conectividad . Cualquier grafo planar maximal puede descomponerse en subgrafos planares maximales con 4 vértices conectados dividiéndolo a lo largo de sus triángulos separadores (triángulos que no son caras del grafo): dado cualquier triángulo no facial, se pueden formar dos grafos planares maximales más pequeños, uno que consiste en la parte dentro del triángulo y el otro que consiste en la parte fuera del triángulo. Los grafos planares maximales sin triángulos separadores 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 biconexos de un grafo que no es biconexo en sí mismo. Una red apolínea es un grafo planar maximal en el que todos los bloques son isomorfos al grafo completo K 4 . 

En la teoría extremal de grafos , las redes apolíneas son también exactamente los grafos planares de n vértices en los que el número de bloques alcanza su máximo, n − 3 , y los grafos planares en los que el número de triángulos alcanza su máximo, 3 n − 8. Dado que cada K 4 subgrafo de un grafo planar debe ser un bloque, estos son también los grafos planares en los que el número de K 4 subgrafos alcanza su máximo, n − 3 , y los grafos en los que el número de camarillas de cualquier tipo alcanza su máximo, 8 n − 16. [ 9 ]

Realizaciones geométricas

Construcción a partir de empaquetamientos circulares

Un ejemplo de junta apolínea
Construcción de una red apolínea a partir de un empaquetamiento circular.

Las redes apolíneas reciben su nombre de Apolonio de Perga , quien estudió el Problema de Apolonio de construir un círculo tangente a otros tres. Un método para construir redes apolíneas consiste en partir de tres círculos tangentes entre sí y luego inscribir repetidamente otro círculo dentro del espacio formado por los tres círculos previamente dibujados. La colección fractal de círculos producida de esta manera se denomina junta apolínea .

Si el proceso de producción de una junta apolínea se detiene prematuramente, con solo un conjunto finito de círculos, entonces el grafo que tiene un vértice por cada círculo y una arista por cada par de círculos tangentes es una red apolínea. [ 10 ] La existencia de un conjunto de círculos tangentes cuyas tangencias representan una red apolínea dada constituye un ejemplo simple del teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston , que establece que cualquier grafo planar puede representarse mediante círculos tangentes de la misma manera. [ 11 ]

Poliedros

El tetraedro triakis , una realización poliédrica de una red apolínea de 8 vértices.

Las redes apolíneas son grafos planares 3-conexos y, por lo tanto, según el teorema de Steinitz , siempre pueden representarse como grafos de poliedros convexos. El poliedro convexo que representa una red apolínea es un politopo apilado tridimensional . Dicho politopo puede obtenerse a partir de un tetraedro añadiendo repetidamente tetraedros adicionales, uno a uno, a sus caras triangulares. Por consiguiente, las redes apolíneas también pueden definirse como grafos de politopos 3D apilados. [ 12 ] Es posible encontrar una representación de cualquier red apolínea como un poliedro 3D convexo en el que todas las coordenadas sean enteros de tamaño polinomial, mejor que la conocida para otros grafos planares. [ 13 ]

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, la denominaron descomposición triangular escalena ternaria . Observaron que, al colocar cada nuevo vértice en el centroide de su triángulo contenedor, la triangulación podía elegirse de tal manera que todos los triángulos tuvieran áreas iguales, aunque no todos tuvieran la misma forma. [ 14 ] 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. [ 15 ]

También es posible llevar a cabo el proceso de subdividir un triángulo para formar una red apolínea de tal manera que, en cada paso, las longitudes de las aristas sean números racionales; es un problema abierto si todo grafo planar tiene un dibujo con esta propiedad. [ 16 ] Es posible en tiempo polinomial encontrar un dibujo de un 3-árbol planar con coordenadas enteras que minimice el área del cuadro delimitador del dibujo, y comprobar si un 3-árbol planar dado puede dibujarse con sus vértices en un conjunto de puntos dado. [ 17 ]

Propiedades y aplicaciones

Gráficos sin coincidencia

Plummer (1992) utilizó redes apolíneas para construir una familia infinita de grafos planares maximales con un número par de vértices, pero sin emparejamiento perfecto . Los grafos de Plummer se forman en dos etapas. En la primera etapa, partiendo de un triángulo abc , se subdivide repetidamente la cara triangular de la subdivisión que contiene la arista bc : el resultado es un grafo que consiste en un camino desde a hasta el vértice de la subdivisión final, junto con una arista desde cada vértice del camino hasta b y c . En la segunda etapa, cada una de las caras triangulares del grafo planar resultante se subdivide una vez más. Si el camino desde a hasta el vértice de la subdivisión final de la primera etapa tiene longitud par, entonces el número de vértices en el grafo general también es par. Sin embargo, aproximadamente 2/3 de los vértices son los insertados 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 emparejamientos para todos ellos. [ 18 ]

Aunque las redes apolíneas en sí mismas pueden no tener emparejamientos perfectos, los grafos duales planares de las redes apolíneas son grafos 3-regulares sin aristas de corte , por lo que, según un teorema de Petersen (1891), se garantiza que tienen al menos un emparejamiento perfecto. 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. [ 19 ] László Lovász y Michael D. Plummer conjeturaron que una cota inferior exponencial similar se cumple de forma más general para todo grafo 3-regular sin aristas de corte, un resultado que posteriormente se demostró.

Gráficas de ley de potencias

Andrade et al. (2005) estudiaron leyes de potencia en las secuencias de grado 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 del espacio por partículas de tamaños variables. Basándose en su trabajo, otros autores introdujeron redes apolíneas aleatorias, formadas al elegir repetidamente una cara aleatoria para subdividir, y demostraron que estas también obedecen leyes de potencia en su distribución de grado [ 20 ] y tienen distancias promedio pequeñas. [ 21 ] Alan M. Frieze y Charalampos E. Tsourakakis analizaron los grados más altos y los valores propios de redes apolíneas aleatorias. [ 22 ] Andrade et al. también observaron que sus redes satisfacen el efecto de mundo pequeño , que todos los vértices están a una distancia pequeña entre sí. Basándose en evidencia numérica, estimaron que la distancia promedio entre pares de vértices seleccionados aleatoriamente 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 . [ 23 ]

Distribución angular

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 que llegan al nuevo vértice bisecan los ángulos del triángulo, entonces el conjunto de ternas de ángulos de triángulos en la subdivisión, cuando se reinterpreta como ternas 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. [ 24 ]

Hamiltonicidad

Takeo (1960) afirmó erróneamente que todas las redes apolíneas tienen ciclos hamiltonianos ; sin embargo, el grafo de Goldner-Harary proporciona un contraejemplo. Si una red apolínea tiene una robustez mayor que uno (lo que significa que al eliminar cualquier conjunto de vértices del grafo queda un número menor de componentes conexas que el número de vértices eliminados), entonces necesariamente tiene un ciclo hamiltoniano, pero existen redes apolíneas no hamiltonianas cuya robustez es igual a uno. [ 25 ]

Enumeración

El problema de enumeración combinatoria del conteo de triangulaciones apolíneas fue estudiado por Takeo (1960) , quien demostró que poseen la función generadora simple f ( x ) descrita por la ecuación f ( x ) = 1 + x ( f ( x )) ³ . 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 el OEIS ) ,

una secuencia que también incluye árboles ternarios y disecciones de polígonos convexos en polígonos de lados impares. Por ejemplo, existen 12 redes apolíneas de 6 vértices: tres formadas al subdividir el triángulo exterior una vez y luego subdividir dos de los triángulos resultantes, y nueve formadas al subdividir el triángulo exterior una vez, subdividir uno de sus triángulos y luego subdividir uno de los triángulos más pequeños resultantes.

Historia

Birkhoff (1930) es un artículo temprano que utiliza una forma dual de redes apolíneas, los mapas planares formados al colocar repetidamente nuevas regiones en los vértices de mapas más simples, como una clase de ejemplos de mapas planares 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 Grünbaum (1963) las utilizó para describir grafos que pueden realizarse como el grafo de un politopo de una sola manera, sin ambigüedades dimensionales ni combinatorias, y Moon y Moser (1963) para encontrar politopos simpliciales sin caminos largos. En teoría de grafos , la estrecha conexión entre planaridad y anchura de árbol se remonta a Robertson y Seymour (1984) , quienes demostraron que toda familia de grafos cerrada en menores tiene una anchura de árbol acotada o contiene todos los grafos planares. Los 3-árboles planares, como clase de grafos, fueron considerados explícitamente por Hakimi y Schmeichel (1979) , Alon y Caro (1984) , Patil (1986) y muchos autores posteriores.

El nombre "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 . [ 26 ] Otros autores aplicaron el mismo nombre de forma más amplia a los 3-árboles planares en su trabajo generalizando el modelo de Andrade et al. a redes apolíneas aleatorias. [ 21 ] Las triangulaciones generadas de esta manera también se han denominado "triangulaciones apiladas" [ 27 ] o "triangulaciones de pila". [ 28 ]

Véase también

Notas

  1. ↑ Este gráfico recibe su nombre del trabajo de Goldner y Harary (1975) ; sin embargo, aparece anteriormente en la literatura, por ejemplo en Grünbaum (1967) , pág. 357.
  2. ↑ Nishizeki (1980) .
  3. ↑ La equivalencia de los 3-árboles planares y los grafos planares maximales cordales fue enunciada sin demostración por Patil (1986) . Para una demostración, véase Markenzon, Justel y Paciornik (2006) . Para una caracterización más general de los grafos planares cordales y un algoritmo de reconocimiento eficiente para estos grafos, véase Kumar y Madhavan (1989) . La observación de que todo grafo poliédrico cordal es planar maximal fue enunciada explícitamente por Gerlach (2004) .
  4. ↑ Fowler (1998) .
  5. ↑ El hecho de que las redes apolíneas minimicen el número de coloraciones con más de cuatro colores fue demostrado en forma dual para coloraciones de mapas por Birkhoff (1930) .
  6. ↑ Felsner y Zickfeld (2008) ; Bernardi y Bonichon (2009) .
  7. ↑ El teorema de Wagner da como resultado los dos menores prohibidos para grafos planares. Para los menores prohibidos de 3-árboles parciales (que incluyen también el grafo de Wagner no planar ), véanse Arnborg, Proskurowski y Corniel (1986) y Bodlaender (1998) . Para demostraciones directas de que el grafo octaédrico y el grafo de prisma pentagonal son los únicos dos menores prohibidos planares, véanse Dai y Sato (1990) y El-Mallah y Colbourn (1990) .
  8. ↑ Politof (1983) introdujo los grafos planares reducibles Δ-Y y los caracterizó en términos de subgrafos homeomorfos prohibidos. La dualidad entre los grafos reducibles Δ-Y e Y-Δ, las caracterizaciones menores prohibidas de ambas clases y la conexión con los 3-árboles parciales planares provienen de El-Mallah y Colbourn (1990) .
  9. ↑ Para la caracterización en términos del número máximo de triángulos en un grafo planar, véase Hakimi y Schmeichel (1979) . Alon y Caro (1984) citan este resultado y proporcionan las caracterizaciones en términos de las clases de isomorfismo de bloques y números de bloques. La cota sobre el número total de cliques se deduce fácilmente de las cotas sobre triángulos y subgrafos K 4 , y también es enunciada explícitamente por Wood (2007) , quien proporciona una red apolínea como ejemplo que muestra que esta cota es ajustada. Para generalizaciones de estas cotas a superficies no planas, véase Dujmović et al. (2009) .
  10. ↑ Andrade et al. (2005) .
  11. ↑ Thurston (1978–1981) .
  12. ^ Véase, por ejemplo, a continuación, De Loera y Richter-Gebert (2000) .
  13. ↑ Demaine y Schulz (2011) .
  14. ↑ Elcock, Gargantini y Walsh (1987) .
  15. ↑ Biedl y Ruiz Velázquez (2010) .
  16. ↑ Para subdividir un triángulo con lados de longitud racional de modo que los triángulos más pequeños también tengan lados de longitud racional, véase Almering (1963) . Para avances en el problema general de encontrar dibujos planos con aristas de longitud racional, véase Geelen, Guo y McKinnon (2008) .
  17. ↑ Para los dibujos con coordenadas enteras, véase Mondal et al. (2010) , y para los dibujos en un conjunto de vértices dado, véase Nishat, Mondal y Rahman (2011) .
  18. ↑ Plummer (1992) .
  19. ↑ Jiménez y Kiwi (2010) .
  20. ↑ Tsourakakis (2011)
  21. 1 2 Zhou et al. (2004) ; Zhou, Yan y Wang (2005) .
  22. ^ Friso y Tsourakakis (2011)
  23. ↑ Albenque y Marckert (2008) ; Zhang et al. (2008) .
  24. ↑ Butler y Graham (2010) .
  25. ↑ Véase Nishizeki (1980) para un ejemplo no hamiltoniano 1-resistente, Böhme, Harant y Tkáč (1999) para la demostración de que las redes apolíneas con mayor resistencia son hamiltonianas, y Gerlach (2004) para una extensión de este resultado a una clase más amplia de grafos planares.
  26. ↑ Grünbaum (1963) ; Grünbaum (1967) .
  27. ↑ Alon y Caro (1984) ; Zickfeld y Ziegler (2006) ; Badent et al. (2007) ; Felsner y Zickfeld (2008) .
  28. ↑ Albenque y Marckert (2008) ; Bernardi y Bonichon (2009) ; Jiménez & Kiwi (2010) .

Referencias

  • Albenque, Marie; Marckert, Jean-François (2008), "Algunas familias de mapas planares 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 un tipo prescrito de grafos planares con un número dado de vértices", en Rosenfeld, M.; Zaks, J. (eds.), Convexidad y teoría de grafos: actas de la Conferencia sobre Convexidad y Teoría de Grafos, Israel, marzo de 1981 , Annals of Discrete Mathematics 20, North-Holland Mathematical Studies 87, Elsevier, pp. 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 apolonias: simultáneamente libres de escala, de mundo pequeño, euclidianas, que llenan el espacio y con grafos coincidentes", Physical Review Letters , 94 (1) 018702, arXiv : cond-mat/0406295 , Bibcode : 2005PhRvL..94a8702A , doi : 10.1103/physrevlett.94.018702 , PMID 15698147 .
  • Arnborg, S.; Proskurowski, A.; Corniel, D. (1986), Forbidden Minors Characterization of Partial 3-trees , Informe técnico CIS-TR-86-07, Departamento de Ciencias de la Computación e Información, Universidad de Oregón. Citado por El-Mallah y Colbourn (1990) .
  • Badent, Melanie; Binucci, Carla; Di Giacomo, Emilio; Dídimo, Walter; Felsner, Stefan; Giordano, Francisco; Kratochvíl, Jan; Palladino, Pietro; Patrignani, Mauricio; Trotta, Francesco (2007), "Representaciones de contacto de triángulos homotéticos de gráficos planos", Conferencia Canadiense sobre Geometría Computacional (PDF).
  • Abajo, Alexander; 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", Journal of Combinatorial Theory , Serie A, 116 (1): 55– 75, doi : 10.1016/j.jcta.2008.05.005 , MR 2469248 .
  • Biedl, Therese ; Ruiz Velázquez, Lesvia Elena (2010), "Dibujo de 3-árboles planares con áreas de caras dadas", Graph Drawing, 17.º Simposio Internacional, GD 2009, Chicago, IL, EE. UU., 22-25 de septiembre de 2009, Artículos revisados , Lecture Notes in Computer Science, vol.  5849, Springer-Verlag, pp. 316-322 , doi : 10.1007/978-3-642-11805-0_30 , ISBN  978-3-642-11804-3.
  • Birkhoff, George D. (1930), "Sobre el número de maneras de colorear un mapa", Actas de la Sociedad Matemática de Edimburgo , (2), 2 (2): 83– 91, doi : 10.1017/S0013091500007598.
  • Bodlaender, Hans L. (1998), "Un k -arboreto parcial de grafos con ancho de árbol acotado", Theoretical Computer Science , 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 grafo planar cordal resistente es hamiltoniano", 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 la Combinatoria y la Informática (PDF) , Bolyai Society Mathematical Studies, vol.  29, Heidelberg: Springer-Verlag, pp . 23–42 .
  • Dai, Wayne Wei-Ming; Sato, Masao (1990), "Caracterización mínima de menores prohibidos de árboles parciales planares de orden 3 y su aplicación al diseño de circuitos", Simposio Internacional IEEE sobre Circuitos y Sistemas , vol.  4, pp. 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", Actas del Simposio ACM-SIAM sobre Algoritmos Discretos (PDF) , págs. 1177–1187 , archivado del original (PDF) el 1 de junio de 2011 , consultado el 7 de marzo de 2011. .
  • Dujmović, Vida ; Fijavž, Gašper; Joret, Gwenaël; Wood, David R. (2009), "El número máximo de camarillas en un grafo 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 grafos planares", 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", Image and Vision Computing , 5 (3): 225– 231, doi : 10.1016/0262-8856(87)90053-9.
  • Felsner, Stefan; Zickfeld, Florian (2008), "Sobre el número de orientaciones planares con grados prescritos" (PDF) , Electronic Journal of Combinatorics , 15 (1): R77, arXiv : math/0701771 , Bibcode : 2007math......1771F , doi : 10.37236/801 , MR 2411454 , S2CID 13893657  .
  • Frieze, Alan M.; Tsourakakis, Charalampos E. (2011), High Degree Vertices, Eigenvalues ​​and Diameter of Random Apollonian Networks , arXiv : 1104.5259 , Bibcode : 2011arXiv1104.5259F.
  • Fowler, Thomas (1998), Coloreado único de grafos planares (PDF) , tesis doctoral, Departamento de Matemáticas del Instituto Tecnológico de Georgia.
  • Geelen, Jim; Guo, Anjie; McKinnon, David (2008), "Incrustaciones de líneas rectas de grafos cúbicos planares con longitudes de aristas enteras", Journal of Graph Theory , 58 (3): 270–274 , doi : 10.1002/jgt.20304 , MR 2419522 .
  • Gerlach, T. (2004), "Resistencia y hamiltonicidad de una clase de grafos planares", Matemáticas Discretas , 286 ( 1–2 ): 61–65 , doi : 10.1016/j.disc.2003.11.046 , MR 2084280 .
  • Goldner, A.; Harary, F. (1975), "Nota sobre el grafo planar maximal no hamiltoniano más pequeño", Bull. Malaysian Math. Soc. , 6 (1): 41– 42Véase 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), "Grafos 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 grafo planar maximal", Journal of Graph Theory , 3 (1): 69–86 , doi : 10.1002/jgt.3190030108 , MR 0519175 .
  • Jiménez, Andrea; Kiwi, Marcos (2010), Counting perfect matchings of cubic graphs in the geometric dual , arXiv : 1010.5918 , Bibcode : 2010arXiv1010.5918J.
  • Kumar, P. Sreenivasa; Madhavan, CE Veni (1989), "Una nueva clase de separadores y planaridad de grafos cordales", Fundamentos de la tecnología del software y la informática teórica, Novena conferencia, Bangalore, India, 19-21 de diciembre de 1989, Actas , Lecture Notes in Computer Science, vol.  405, Springer-Verlag, pp. 30-43 , doi : 10.1007/3-540-52048-1_30 , ISBN  978-3-540-52048-1, MR 1048636 .
  • Markenzon, L.; Justel, CM; Paciornik, N. (2006), "Subclases de k- árboles: 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 3-árboles planos", Conferencia Canadiense sobre Geometría Computacional (PDF).
  • Moon, JW; Moser, L. (1963), "Simple paths on polyhedra" , 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), "Incrustaciones de conjuntos de puntos de 3-árboles planos", Dibujo de grafos, 18.º Simposio Internacional, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Artículos seleccionados revisados , Lecture Notes in Computer Science, vol.  6502, Springer-Verlag, pp. 317-328 , doi : 10.1007/978-3-642-18469-7_29 , ISBN  978-3-642-18468-0.
  • Nishizeki, Takao (1980), "Un grafo planar maximal no hamiltoniano 1-resistente", Matemáticas Discretas , 30 (3): 305–307 , doi : 10.1016/0012-365X(80)90240-X , MR 0573648 .
  • Patil, HP (1986), "Sobre la estructura de los k -árboles", 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), "Extending matchings in planar graphs IV", Discrete Mathematics , 109 ( 1– 3): 207– 219, doi : 10.1016/0012-365X(92)90292-N , MR 1192384 .
  • Politof, T. (1983), Caracterización y cálculo eficiente de la fiabilidad de redes reducibles Δ-Y , tesis doctoral, Universidad de California, Berkeley. 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 , MR 0742386 .
  • Takeo, Fujio (1960), "Sobre grafos triangulados. I", Bull. Fukuoka Gakugei Univ. III , 10 : 9– 21, MR 0131372 WT Tutte, revisor de MathSciNet, señaló un error relacionado con la hamiltonicidad .
  • Thurston, William (1978–1981), La geometría y topología de las 3-variedades , apuntes de clase 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 grafo", Graphs and Combinatorics , 23 (3): 337–352 , arXiv : math/0602191 , doi : 10.1007/s00373-007-0738-8 , MR 2320588 , S2CID 46700417  .
  • Zhang, Zhongzhi; Chen, Lichao; Zhou, Shuigeng; Colmillo, 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 grado de ley de potencias", 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 sobre combinatoria geométrica y topológica (PDF).