Abstract-We initierar studien av testbarheten av egenskaper i godtyckliga planar grafer. Vi bevisar att tvåpartighet kan testas i konstant tid. Den tidigare bundet för denna klass av grafer var Õ( ε n), och konstant-tid testbarheten var endast känd för planar grafer med begränsad grad. Tidigare använda omvandlingar av obundna glesa grafer till limmade glesa grafer kan inte användas för att minska problemet till testbarheten av plana grafer med begränsad grad. Vårt tillvägagångssätt sträcker sig till godtyckliga mindre fria grafer. Vår algoritm är baserad på slumpmässiga promenader. Utmaningen här är att analysera slumpmässiga promenader för en grupp grafer som har bra separatorer, d.v.s. dålig expansion. Standardtekniker som använder en snabb konvergens till en enhetlig fördelning fungerar inte i detta fall. Grovt taget minskar vår analysteknik själv problemet med att hitta en udda längdcykel i en multigraf G inducerad av en samling cykler till en annan multigraf G inducerad av en uppsättning kortare udda-längd cykler, på ett sådant sätt att när en slumpmässig promenader finner en cykel i G med sannolikhet p > 0, då gör det så med sannolikhet λ(p) > 0 i G. Denna minskning tillämpas tills cyklerna kollapsar till självloopar som lätt kan upptäckas.
Test av tvåpartiitet i plana grafer studerades i REF.
Planar Graphs: Random Walks and Bipartiteness Testing
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}