Schnelle Löschung / Kontraktion bei kombinatorischer Einbettung

Ich frage mich, ob es einen sublinearen Algorithmus gibt, mit dem eine Kante in einer kombinatorischen Einbettung von beispielsweise einem planaren Graphen gelöscht oder kontrahiert werden kann.

Da bei der kombinatorischen Einbettung gleichzeitig die Eckpunkte von G und G * beibehalten werden müssen, wobei zu berücksichtigen ist, dass die Kontraktion im Primären eine Deletion im Dualen ist, reicht es aus, nur Löschungen vorzunehmen und die Primalpermutation gemäß Dual zu aktualisieren und umgekehrt . Ein offensichtlicher Weg, dies zu tun, besteht darin, sie neu zu berechnen, was lineare Zeit in Anspruch nimmt. Können wir es besser machen?

Zweite Frage : Gibt es eine Technik, mit der mehrere Kanten zwischen denselben Scheitelpunkten entfernt werden können? (Die einzige Lösung, die ich für das zweite Problem sehe, besteht darin, das Löschen mehrerer Kanten zu verschieben, bis wir einen Graphen mit beispielsweise m = 6n erhalten, wobei m - Anzahl der Kanten, n - Anzahl der Eckpunkte, wodurch die Zeit amortisiert wird (1)) Vielleicht gibt es einige Techniken, die dazu führen können, dass diese Zeit nicht amortisiert wird? (Ich interessiere mich auch nur für o (n) Lösungen, nicht unbedingt für O (1))

Vielen Dank!

Diese Frage ist unvollständig, ohne anzugeben, welche Informationen über das Diagramm sich ändern, wenn Ihre dynamische Diagrammdatenstruktur Abfragen ausgeben oder unterstützen soll. Das folgende Papier ist jedoch wahrscheinlich relevant, obwohl es in einer allgemeineren Umgebung kombinatorischer Einbettungen in beliebige Gattungen und nicht nur planar beschrieben wird. Es unterstützt definitiv sowohl Kontraktionen und Löschungen als auch deren umgekehrte Operationen in logarithmischer Zeit pro Operation.

Dynamische Generatoren topologisch eingebetteter Graphen. D. Eppstein. arXiv: cs.DS / 0207082 . SODA 2003, S. 599-608.

Was die zweite Frage betrifft: Ich sehe im Allgemeinen nicht, wie man mit mehreren Nachbarschaften umgeht, aber es ist einfach, Bigons (mehrere Kanten mit nichts dazwischen) loszuwerden, da sie nur von den beiden Gesichtern kommen können, die sich auf beiden Seiten befinden eine kontrahierte Kante oder von der Fläche, die eine gelöschte Kante umgibt. Dies sollte für viele Zwecke ausreichen, da durch das Entfernen der Bigons sichergestellt wird, dass der verbleibende Graph eine Anzahl von Kanten aufweist, die proportional zu seiner Anzahl von Scheitelpunkten ist.