Vi beskriver algoritmer och datastrukturer för att upprätthålla en dynamisk planar graf som är föremål för kantinsättningar och kantraderingar som bevarar planaritet men som kan ändra inbäddningen. Vi ger en helt dynamisk planarity testalgoritm som upprätthåller en graf som är föremål för kantinsättningar och raderingar och som tillåter frågor som testar om grafen för närvarande är planar, eller om en potentiell ny kant skulle bryta planaritet, i O(n 1Â2 ) amortized tid per uppdatering eller fråga. Vi ger helt dynamiska algoritmer för att upprätthålla de anslutna komponenterna, den bästa swap och minsta spännvidd skog av en planar graf i O(log n) värsta fall tid per insättning och O(log 2 n) per radering. Slutligen ger vi helt dynamiska algoritmer för att upprätthålla de 2-kantsanslutna komponenterna i en planar graf i O(log n) avkortad tid per insättning och O(log 2 n) per radering. Alla datastrukturer, förutom den som besvarar planaritetsförfrågningar, hanterar endast tillägg som håller grafen planar. Alla våra algoritmer förbättrar tidigare gränser. Förbättringarna baseras på en ny typ av sparifiering i kombination med flera egenskaper hos avskiljare i plana grafer. ]
För konnektivitetsmåttet Eppstein et al. REF ger en algoritm med O(log 2 n) avkortad uppdateringstid och O(log n) frågetid.
Separator based sparsification. I. Planarity testing and minimum spanning trees
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}