Complejidad temporal del recuento de triángulos en gráficos planos

El recuento de triángulos en gráficos generales se puede hacer trivialmente en el tiempo y creo que hacer mucho más rápido es difícil (se aceptan referencias). ¿Qué pasa con los gráficos planos? El siguiente procedimiento sencillo muestra que se puede hacer en tiempo . Mi pregunta es doble:$O(n^3)$$O(n\log{n})$

• ¿Qué es una referencia para este procedimiento?
• ¿Se puede hacer el tiempo lineal?

A partir de la prueba algorítmica del teorema del separador plano de Lipton-Tarjan, podemos, en un tiempo lineal en el tamaño del gráfico, encontrar una partición de vértices del gráfico en tres conjuntos modo que no haya bordes con un punto final en y el otro en , tiene un tamaño limitado por y ambos tienen tamaños superiores delimitados por del número de vértices. Observe que cualquier triángulo en el gráfico yace completamente dentro de o completamente dentro de o usa al menos un vértice de con los otros dos vértices de o ambos de$A,B,S$$A$$B$$S$$O(\sqrt{n})$$A,B$$\frac{2}{3}$$A$$B$$S$$A \cup S$$B \cup S$ . Por lo tanto, es suficiente contar el número de triángulos en el gráfico en y los vecinos de en (y de manera similar para ). Observe que y sus vecindarios inducen un gráfico plano exterior (dicho gráfico es un subgrafo de un gráfico plano de diámetro ). Por lo tanto, el recuento del número de triángulos en un gráfico de este tipo se puede hacer directamente mediante programación dinámica o mediante una aplicación del teorema de Courcelle (sé con certeza que existe una versión de conteo en el mundo de Logspace por Elberfeld et al y supongo que también existe en el mundo del tiempo lineal) ya que formar un triángulo no dirigido es una$S$$S$$A$$B$$S$$A$$k$$4$$\mathsf{MSO}_1$ y dado que una descomposición del árbol de ancho acotado es fácil de obtener de un gráfico plano -outer incrustado .$k$

Por lo tanto, hemos reducido el problema a un par de problemas, cada uno de los cuales es una fracción constante más pequeña a expensas de un procedimiento de tiempo lineal.

Observe que el procedimiento puede extenderse para encontrar el recuento del número de instancias de cualquier gráfico conectado fijo dentro de un gráfico de entrada en tiempo .$O(n\log{n})$

El número de ocurrencias de cualquier subgrafo fijo H en un gráfico plano G se puede contar en el tiempo O (n), incluso si H está desconectado. Esto, y varios resultados relacionados, se describen en el artículo Subgraph Isomorphism in Planar Graphs and Related Problems de David Eppstein de 1999; ver Teorema 1. El documento de hecho usa técnicas de ancho de árbol.

Aunque la respuesta de Bart Jansen resuelve el caso general del recuento de subgrafos, se sabe que el problema de contar (o enumerar) todos los triángulos en un gráfico plano (o más generalmente cualquier gráfico de arboricidad limitada) es tiempo lineal durante mucho más tiempo. Ver

C. Papadimitriou y M. Yannakakis, El problema de la camarilla para los gráficos planos, Inform. Proc. Letters 13 (1981), págs. 131-133.

y

N. Chiba y T.Nishizeki, Arboricity y algoritmos de listado de subgrafos, SIAM J. Comput. 14 (1985), págs. 210–223.