Pfadbreite der planarisierten Zeichnung von

Die Pfadbreite des vollständigen zweigliedrigen Graphen mit Teilmengen der Größe 3 und n beträgt höchstens 3 . Ich bin daran interessiert, dieses Diagramm nach folgendem Verfahren zu planarisieren:$K_{3,n}$$3$$n$$3$

1. Zeichnen Sie es in der Ebene so, dass keine Kante einen Scheitelpunkt in ihrem Inneren enthält und dass sich an keiner Stelle mehr als 2 Kanten kreuzen.
2. Ersetzen Sie jeden Kreuzungspunkt zweier Kanten durch einen neuen Scheitelpunkt 4. Grades.

Dann ist der resultierende Graph klar planar. Während eine konstante Pfadbreite hat, legen einige vorläufige Untersuchungen nahe, dass Sie unabhängig von der Zeichnung, die Sie zum Planarisieren von K 3 , n verwenden , nicht garantieren können, dass der planarisierte Graph unabhängig von n eine konstante Pfadbreite aufweist . Ich glaube, die Pfadbreite des planarisierten Graphen muss mit n wachsen . Ist dies bekannt oder impliziert es ein vorhandenes Ergebnis?$K_{3,n}$$K_{3,n}$$n$$n$

Andererseits habe ich eine Familie von Graphen mit konstantem Grad und begrenzter Pfadbreite, die ich planarisieren kann, ohne die Pfadbreite um mehr als eine Konstante zu erhöhen. Gibt es ein allgemeines Ergebnis, das besagt, dass dies für Graphen mit begrenztem Grad und Pfadbreite immer möglich ist?

$K_{3,n}$$O(n)$$\Omega(n)$

$K_{3,n}$$K_{3,3}$$K_{3,n}$$n-2$$K_{3,3}$$\tbinom{n}{3}$ $K_{3,3}$$n^2/6$$n^2/4$

$S$$K_{3,n}$

$S$$S$$S$

$\epsilon n$$\epsilon$$\Omega(n)$$\Omega(n)$

$S$$S$$S$$S$$S$

$S$

Was Ihren Vorschlag betrifft, dass Diagramme mit begrenzter Pfadbreite begrenzte Layouts haben, deren Planarisierung die Pfadbreite begrenzt hat: Dies scheint tatsächlich wahr zu sein.

$O(1)$$O(1)$. Wenn Sie einen neuen Scheitelpunkt erreichen, können Sie den Spuren anderer Scheitelpunkte, die mit ihm verbunden werden sollen, nahezu vertikale Konnektoren und kürzere Verbindungen zu den ausgehenden Spuren hinzufügen. Hier ist ein Beispiel mit der Scheitelpunkttrennung Nummer drei, Grad drei und drei Spuren pro Scheitelpunkt.

$O(1)$