Verallgemeinerte planare Graphen und verallgemeinerte äußere planare Graphen

Jede planare bzw. outerplanar Graph erfüllt , jeweils , für jeden Untergraphen von . Auch (äußere) planare Graphen können in Polynomzeit erkannt werden.| E ' | ≤ 3 | V ' | - 6 | E ' | ≤ 2 | V ' | - 3 G ' = ( V ' , E ' ) $G=(V,E)$$|E'|\le 3|V'|-6$
$|E'|\le 2|V'|-3$$G'=(V',E')$$G$

Was ist über Graphen so dass (bzw. ) für jeden Teilgraphen von ? Ist es möglich, sie in der Polynomzeit zu erkennen?| E ' | ≤ 3 | V ' | - 6 | E ' | ≤ 2 | V ' | - 3 G ' = ( V ' , E ' ) $G=(V,E)$$|E'|\le 3|V'|-6$$|E'|\le 2|V'|-3$$G'=(V',E')$$G$

Edit (nach Eppsteins netter Antwort): Jeder planare Graph erfüllt für jeden Teilgraphen von mit mindestens drei Eckpunkte . "Verallgemeinerte planare Graphen" wären also diejenigen, die diese Eigenschaft erfüllen, und ihre Erkennung in der Polynomzeit scheint eine (interessante) offene Frage zu sein.| E ' | ≤ 3 | V ' | - 6 G ' = ( V ' , E ' ) G | V ' | ≥ $G=(V,E)$$|E'|\le 3|V'|-6$$G'=(V',E')$$G$ $|V'|\ge 3$

In der Notation von Lee und Streinu (siehe unten) sind die (2,3) -sparsamen Graphen die zweite Klasse, die Sie auflisten. Sie geben einen Algorithmus an, um zu testen, ob ein Graph in der Polynomzeit (k, l) -sparsam ist. Die Situation mit planaren Graphen und ist jedoch etwas komplizierter, da diese Ungleichung nicht für alle Gruppen von Scheitelpunkten gilt (wenn dies der Fall wäre, könnten keine zwei Scheitelpunkte verbunden werden) durch eine Kante, weil ). Die Klasse der (3,6) -sparsen Graphen (in ihrer Notation) besteht also nur aus leeren Graphen. Wahrscheinlich können ihre Algorithmen auf Graphen ausgedehnt werden, für die die Ungleichung für alle Mengen von mehr als zwei Eckpunkten gilt.3 ⋅ 2 - 6 = $|E'|\le 3|V'|-6$$3\cdot 2-6=0$

Lee, Audrey; Streinu, Ileana (2008), "Pebble Game Algorithms and Sparse Graphs", Discrete Mathematics 308 (8): 1425–1437, doi: 10.1016 / j.disc.2007.07.104 , arxiv: math / 0702129 .

Was ist über "verallgemeinerte äußere planare Graphen" oder (2,3) -sparsame Graphen bekannt? Einige zusätzliche Fakten zu DavidEppsteins Antwort:

In dieser Arbeit (Korollar 1 und 2) charakterisierten Lovász und Yemini 1982 verallgemeinerte äußere ebene Graphen (in ihrer Notation generische unabhängige Graphen ) als solche Graphen mit der Eigenschaft, dass das Verdoppeln einer beliebigen Kante von zu einem Graphen führt, der die Kante ist -disjunkte Vereinigung zweier Wälder.$G$$G$

Bereits 1970 haben Henneberg und Laman bewiesen, dass verallgemeinerte äußere ebene Graphen rekursiv aus durch drei sogenannte Henneberg-Bewegungen erhalten werden können (Hinzufügen eines Scheitelpunkts vom Grad 1, Hinzufügen eines Scheitelpunkts vom Grad 2 und einer bestimmten Art des Hinzufügens eines Grades) -3 Vertex).$K_2$

Diese Charakterisierungen liefern die ersten polynomiellen Erkennungen für verallgemeinerte äußere ebene Graphen.

Einige Bemerkungen im Zusammenhang zu verallgemeinern planaren Graphen können im letzten Abschnitt findet dieses Papier . Ich denke, die Charakterisierung und das Erkennen von verallgemeinerten planaren Graphen bleiben immer noch sehr interessante offene Fragen.