Abstrakt. Vi anser att problemet med att upprätthålla en dynamisk planar graf är föremål för kantinsättningar och kantraderingar som bevarar planaritet men som kan ändra inbäddningen. Vi beskriver algoritmer och datastrukturer för att upprätthålla information om 2- och 3-vertex-konnektivitet, och 3- och 4-kant-konnektivitet i en planar graf i O(n 1/2 ) amorterad tid per insättning, radering, eller konnektivitetsfråga. Alla datastrukturer hanterar ingångar som håller grafen planar utan hänsyn till någon särskild inbäddning av grafen. Våra algoritmer bygger på en ny typ av sparifiering i kombination med flera egenskaper hos avskiljare i plana grafer. Nyckelord. Analys av algoritmer, dynamiska datastrukturer, kantanslutning, vertex-anslutning, planar grafer AMS ämnesklassificeringar. 68P05, 68Q20, 68R10 PII. S0097539794269072 1. Inledning. Sparse certifikat, små grafer som behåller viss egenskap hos en större graf, visas ofta i grafteori, särskilt i problem med kant och vertex anslutning [2, 13, 31, 35]. Den främsta motivationen för att studera sparsamma certifikat ligger i det faktum att de är effektiva verktyg för att påskynda många grafalgoritmer. För att kontrollera om en graf G har en given egenskap P, kan man först beräkna ett sparsamt certifikat C för egenskap P och sedan köra en algoritm för P på certifikatet snarare än på själva G. Detta är fördelaktigt när datorcertifikat är snabbare än att kontrollera egenskap P. Denna metod har lett till förbättrade algoritmer för att testa k-edgeand k-vertex-anslutning i följd [16, 31, 35] och parallellt [2], för att hitta tre oberoende spännvidd träd [1], och för tillförlitlighet i distribuerade nätverk [26]. Med sparifieringstekniken [8] blev sparsamma certifikat dessutom ett viktigt verktyg för att påskynda dynamiska grafalgoritmer, där kanter kan infogas i och tas bort från en graf medan vissa grafegenskaper måste bibehållas under hela sekvensen av ändringar.
Eppstein m.fl. REF ger en O(n) tidsalgoritm för testning av k-edge-anslutning för k ≤ 4 och k-vertex-anslutning för k ≤ 3.
Separator-Based Sparsification II: Edge and Vertex Connectivity
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}