Złożoność czasowa liczenia trójkątów na wykresach płaskich

Liczenie trójkątów na ogólnych wykresach można trywialnie wykonać w czasie i myślę, że znacznie szybsze wykonanie jest trudne (mile widziane referencje). Co z grafami płaskimi? Poniższa prosta procedura pokazuje, że można tego dokonać w czasie O ( n log n ) . Moje pytanie jest dwojakie:$O(n^3)$$O(n\log{n})$

• Jakie jest odniesienie do tej procedury?
• Czy czas może być liniowy?

Z algorytmicznego dowodu twierdzenia Liptona-Tarjana o separatorze planarnym możemy, w czasie liniowym w wielkości wykresu, znaleźć podział wierzchołków wykresu na trzy zestawy tak że nie ma żadnych krawędzi z jednym punktem końcowym w A i drugi w B , S ma rozmiar ograniczony przez O ( $A,B,S$$A$$B$$S$i obaA,Bmają rozmiary górne ograniczone przez$O(\sqrt{n})$$A,B$ liczby wierzchołków. Należy zauważyć, że każdy trójkąt wykres leży całkowicie wewnątrz alboA,albo całkowicie wewnątrzB,lub stosuje się co najmniej jeden wierzchołekSz dwoma innymi wierzchołkiA∪Slub obu z nichB∪S. Wystarczy zatem zliczyć liczbę trójkątów na wykresie naSi sąsiadówSnaA(i podobnie dlaB). Zauważ, żeSi jego-Asąsiadują indukująpłaski wykresk-routera (wspomniany wykres jest podgraphem płaskiego wykresu o średnicy$\frac{2}{3}$$A$$B$$S$$A \cup S$$B \cup S$$S$$S$$A$$B$$S$$A$$k$$4$). Tak więc zliczanie liczby trójkątów na takim wykresie można wykonać bezpośrednio przez programowanie dynamiczne lub przez zastosowanie twierdzenia Courcelle (wiem na pewno, że taka wersja zliczania istnieje w świecie Logspace autorstwa Elberfelda i in. I domyślam się, że ona również istnieje w liniowym świecie czasu), ponieważ tworzenie niekierowanego trójkąta jest właściwością i ponieważ rozkład drzewa o ograniczonej szerokości jest łatwy do uzyskania z osadzonego płaskiego wykresu k- routera.$\mathsf{MSO}_1$$k$

W ten sposób zredukowaliśmy problem do pary problemów, z których każdy jest stałą częścią mniejszą kosztem liniowej procedury czasowej.

Zauważ, że procedurę można rozszerzyć, aby znaleźć liczbę wystąpień dowolnego połączonego grafu wewnątrz wykresu wejściowego w czasie .$O(n\log{n})$

Liczbę wystąpień dowolnego stałego wykresu podrzędnego H na wykresie planarnym G można policzyć w czasie O (n), nawet jeśli H jest odłączony. To i kilka powiązanych wyników opisano w artykule Subgraf Isomorphism in Planar Graphs and Related Problems autorstwa Davida Eppsteina z 1999 r .; patrz Twierdzenie 1. Artykuł rzeczywiście używa technik treewidth.

Chociaż odpowiedź Barta Jansena rozwiązuje ogólny przypadek zliczania podgrafów, problem zliczania (lub notowania) wszystkich trójkątów na wykresie planarnym (lub bardziej ogólnie dowolnego wykresu ograniczonej arborności) jest znany z tego, że czas liniowy jest znacznie dłuższy. Widzieć

C. Papadimitriou i M. Yannakakis, Problem kliki dla grafów płaskich, Inform. Proc. Letters 13 (1981), s. 131–133.

i

N. Chiba i T.Nishizeki, Algorytmy arboryczności i listowania podgraficznego, SIAM J. Comput. 14 (1985), s. 210–223.