Abstrakt. Vi presenterar I/O-effektiva algoritmer för att beräkna optimala separationer av plana grafer. Vårt huvudsakliga resultat visar att, med tanke på en planar graf G med N hörn och ett heltal r > 0, en vertex separator av storlek O(N/ ε r) som partitionerar G i O(N/r) subgrafer av storlek som mest r och gränsstorlek O( ε r) kan beräknas i O(sort(N )) I/Os. Denna gräns gäller under förutsättning att M ≥ 56r log 2 B. Tillsammans med en I/O-effektiv planar inbäddande algoritm presenteras i [33], Detta resultat är grunden för I/O-effektiva lösningar på många andra grundläggande problem på planar grafer, inklusive bredd-första sökning och kortaste vägar [5, 8], djup-första sökning [6, 9], stark konnektivitet [9], och topologisk sortering [7, 8]. Vårt andra resultat visar att med tanke på I/O-effektiva lösningar på dessa problem kan en allmän avskiljaralgoritm för grafer med kostnader och vikter på hörnen [3] göras I/O-effektiv. Många klassiska separatorem är speciella fall av detta resultat. I synnerhet gör vår I/O-effektiva version det möjligt att beräkna en separator som produceras av vår första separatoralgoritm, men utan att sätta några begränsningar på r i förhållande till minnesstorleken.
Maheshwari och Zeh REF visade att en sådan partition av en planar graf kan beräknas I/O-effektivt med O(sort(V ) I/Os förutsatt att M min(cB 2, cR log 2 B), för en tillräckligt stor konstant c. Alla I/O-effektiv planar graf algoritmer först beräkna en partition av grafen med R =  till (B 2 ) och använda den för att minska det ursprungliga problemet till ett mindre problem, definieras på den (V /B) separator hörn.
I/O-efficient planar separators
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}