Pfadbreite der planarisierten Zeichnung von

8

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:K3,n3n3

  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?K3,nK3,nnn

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?

Bart Jansen
quelle

Antworten:

10

K3,nO(n)Ω(n)

K3,nK3,3K3,nn2K3,3(n3) K3,3n2/6n2/4

SK3,n

SSS

ϵnϵΩ(n)Ω(n)

SSSSS

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.

Geben Sie hier die Bildbeschreibung ein

O(1)

David Eppstein
quelle
Schöne und sehr aufschlussreiche Antwort David, vielen Dank! Ich hatte gehofft, dass eine Verbindung zu "Track-Layouts" auftauchen würde. Es stellt sich heraus, dass die Graphfamilie, die ich habe und die höchstens 4 Grad hat, tatsächlich planarisiert werden kann, während die Pfadbreite um höchstens eine additive Konstante erhöht wird . Es würde mich wundern, wenn man für Graphen der Stufe 4 im Allgemeinen nur eine additive Erhöhung erzielen kann.
Bart Jansen
K2,3K3,n
Ups, ja, behoben.
David Eppstein