Eine weitere Frage zum planaren Separator

Kennt jemand von euch eine Referenz für das folgende (überraschend mühsame) Ergebnis?

Bei einem verbundenen planaren Graphen mit Eckpunkten und Kanten hat er einen Eckpunkttrenner der Größe $G$ $n$ $n+t$ . $O( \sqrt{t}+1)$

reference-request planar-graphs separation Sariel Har-Peled
quelle

Ist es wirklich so langweilig? Sie haben höchstens

Blöcke, ziehen sie in Eckpunkte zusammen und verwenden für sie den Satz des gewichteten Trennzeichens. Wenn die Trennblöcke groß sind, können Sie alle

zerstören

t

$t$

Kanten zwischen ihnen und dann jeweils willkürlich mit jeweils zwei Eckpunkten trennen.

O (\sqrt{t})

$O(\sqrt t)$

Domotorp

Was ist die genaue Definition der Blöcke?

Sariel Har-Peled

Benötigen Sie wirklich die

+ 1

$+1$

O (\cdot)

$O(\cdot)$

Aryeh

Ja. Wenn t Null ist ...

Sariel Har-Peled

@domotorp Übrigens, ich glaube nicht, dass Ihre Idee funktioniert - das gesamte Diagramm könnte ein einzelner Block sein - denken Sie nur an einen Pfad und eine zusätzliche Kante, die die beiden Endpunkte verbindet, und an einige andere Kanten ...

Sariel Har-Peled

Antworten:

Hier ist ein Beweis mit einem bekannten Hammer.

$G$ $t+1$ $G$ $t+1$

$G$ $O(\sqrt{t})$ $k$ $G$ $G$ $\Omega(k)$ $\Omega(k)$ $\Omega(k^2)$ $t+1$ $k = O(\sqrt{t})$

Chandra Chekuri
quelle

G

$G$

t

$t$

G

$G$

O (\sqrt{t})

$O(\sqrt{t})$

Der zitierte Satz von Robertson Seymour Thomas hat einen relativ kurzen, in sich geschlossenen Beweis, es ist also kein so großer Hammer.

Daniello

Bearbeitet, um "großen", aber beibehaltenen "Hammer" zu entfernen.

Chandra Chekuri

@ Daniello ist das nicht Graph Minor V?

Saeed