Informacje o uogólnionych grafach płaskich i uogólnionych grafach zewnętrznych płaszczyzn

Każdy płaski odpowiednio outerplanar wykres spełnia , odpowiednio | E ′ | ≤ 2 | V ′ | - 3 dla każdego podgrafu G ' = ( V ' , E ' ) z G . Również (zewnętrzne) wykresy płaskie można rozpoznać w czasie wielomianowym.$G=(V,E)$$|E'|\le 3|V'|-6$
$|E'|\le 2|V'|-3$$G'=(V',E')$$G$

Co wiadomo na temat wykresów tak że | E ′ | ≤ 3 | V ′ | - 6 (odpowiednio | E ′ | ≤ 2 | V ′ | - 3 ) dla każdego podgrupy G ′ = ( V ′ , E ′ ) z G ? Czy można je rozpoznać w czasie wielomianowym?$G=(V,E)$$|E'|\le 3|V'|-6$$|E'|\le 2|V'|-3$$G'=(V',E')$$G$

Edycja (po ładnej odpowiedzi Eppsteina): Każdy płaski wykres spełnia | E ′ | ≤ 3 | V ′ | - 6 dla każdej podgrafu G ' = ( V ' , E ' ) z G z co najmniej trzema wierzchołkami | V ′ | ≥ $G=(V,E)$$|E'|\le 3|V'|-6$$G'=(V',E')$$G$ $|V'|\ge 3$. Zatem „uogólnionymi wykresami planarnymi” byłyby te spełniające tę właściwość, a rozpoznanie ich w czasie wielomianowym wydaje się (interesujące) otwartym pytaniem.

$|E'|\le 3|V'|-6$$3\cdot 2-6=0$). Zatem klasa (3,6) rzadkich wykresów (w ich zapisie) składa się tylko z pustych wykresów. Prawdopodobnie ich algorytmy można rozszerzyć na wykresy, dla których nierówność obowiązuje dla wszystkich zestawów więcej niż dwóch wierzchołków.

Lee, Audrey; Streinu, Ileana (2008), „Algorytmy gry Pebble i rzadkie wykresy”, Discrete Mathematics 308 (8): 1425–1437, doi: 10.1016 / j.disc.2007.07.104 , arxiv: math / 0702129 .

Co wiadomo na temat „uogólnionych zewnętrznych wykresów płaszczyznowych” lub (2,3) rzadkich wykresów? Kilka dodatkowych faktów do odpowiedzi DavidEppstein:

$G$$G$

$K_2$przez trzy tak zwane ruchy Henneberga (dodanie wierzchołka stopnia 1, dodanie wierzchołka stopnia 2 oraz pewien rodzaj dodania wierzchołka stopnia 3).

Charakterystyka ta daje pierwsze rozpoznanie wielomianowe dla uogólnionych grafów płaszczyzny zewnętrznej.

Kilka uwag dotyczących uogólnionych grafów płaskich można znaleźć w ostatniej części tego artykułu . Myślę, że scharakteryzowanie i rozpoznanie uogólnionych wykresów planarnych wciąż pozostaje bardzo interesującymi otwartymi pytaniami.