Zeitliche Komplexität beim Zählen von Dreiecken in ebenen Diagrammen

Das Zählen von Dreiecken in allgemeinen Diagrammen kann trivial in und ich denke, dass es schwierig ist, viel schneller zu arbeiten (Referenzen erwünscht). Was ist mit planaren Graphen? Das folgende unkomplizierte Verfahren zeigt, dass es in O ( n log n ) Zeit durchgeführt werden kann. Meine Frage ist zweifach:$O(n^3)$$O(n\log{n})$

• Was ist eine Referenz für dieses Verfahren?
• Kann die Zeit linear gemacht werden?

Aus dem algorithmischen Beweis von Lipton-Tarjans Planar-Separator-Theorem können wir zeitlich linear in der Größe des Graphen eine Aufteilung der Scheitelpunkte des Graphen in drei Mengen so dass es keine Kanten mit einem Endpunkt gibt A und der andere in B , S hat eine durch O begrenzte Größe ( $A,B,S$$A$$B$$S$und beideA,Bhaben Größenobergrenzen von$O(\sqrt{n})$$A,B$ der Anzahl der Eckpunkte. Beachten Sie, dass jedes Dreieck in der Grafik entweder vollständig innerhalb vonAoder vollständig innerhalb vonB liegtoder mindestens einen Scheitelpunkt vonSmit den beiden anderen Scheitelpunkten vonA∪Soder beiden vonB∪S verwendet. Daher genügt es, die Anzahl der Dreiecke in der Grafik aufSund die Nachbarn vonSinA(und ähnlich fürB) zu zählen. Beachten Sie, dassSund seineA-Nachbarn einenplanarenk-outer-Grapheninduzieren(der Graph ist ein Subgraph eines planaren Graphen mit Durchmesser$\frac{2}{3}$$A$$B$$S$$A \cup S$$B \cup S$$S$$S$$A$$B$$S$$A$$k$$4$). Das Zählen der Anzahl der Dreiecke in einem solchen Graphen kann also direkt durch dynamische Programmierung oder durch Anwendung des Courcelle-Theorems erfolgen (ich weiß mit Sicherheit, dass eine solche Zählversion in der Logspace-Welt von Elberfeld et al. Existiert und vermute, dass sie auch existiert in der linearen Zeit Welt) , da ein eine ungerichtete Dreieck bildet , ist Eigenschaft und da eine beschränkte Breite Baumzerlegung ist leicht von einem eingebetteten zu erhalten , k -Außen- planar Graphen.$\mathsf{MSO}_1$$k$

Somit haben wir das Problem auf ein Paar von Problemen reduziert, die auf Kosten eines linearen Zeitverfahrens jeweils einen konstanten Bruchteil kleiner sind.

Beachten Sie, dass die Prozedur erweitert werden kann, um die Anzahl der Instanzen eines fest verbundenen Graphen innerhalb eines Eingabegraphen in -Zeit zu ermitteln.$O(n\log{n})$

Die Anzahl der Vorkommen eines festen Teilgraphen H in einem planaren Graphen G kann in O (n) -Zeit gezählt werden, selbst wenn H nicht verbunden ist. Dies und einige verwandte Ergebnisse sind in der Veröffentlichung Subgraph Isomorphism in Planar Graphs und Related Problems von David Eppstein von 1999 beschrieben. siehe Theorem 1. In der Tat werden in der Arbeit Baumweitentechniken verwendet.

Obwohl Bart Jansens Antwort den allgemeinen Fall des Zählens von Untergraphen löst, ist bekannt, dass das Problem des Zählens (oder Auflistens) aller Dreiecke in einem planaren Graphen (oder allgemein eines Graphen mit beschränkter Arborität) eine viel längere lineare Zeit ist. Sehen

C. Papadimitriou und M. Yannakakis, Das Cliquenproblem für planare Graphen, Inform. Proc. Letters 13 (1981), S. 131–133.

und

N. Chiba und T. Nishizeki, Arboricity und Subgraph Listing Algorithmen, SIAM J. Comput. 14 (1985), S. 210–223.