Tentang grafik planar yang digeneralisasi dan grafik outerplanar yang digeneralisasi

Setiap planar , masing-masing, outerplanar graph memenuhi , masing-masing, , untuk setiap subgraf dari . Juga, grafik planar (luar) dapat dikenali dalam waktu polinomial.| 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$

Apa yang diketahui tentang grafik sedemikian rupa sehingga (resp. ) untuk setiap subgraf G '= (V ', E') dari G ? Apakah mungkin mengenalinya dalam waktu polinomial?| 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$

Mengedit (setelah Eppstein ini bagus jawaban): Setiap planar graph $G=(V,E)$ memenuhi $|E'|\le 3|V'|-6$ untuk setiap subgraf $G'=(V',E')$ dari $G$ dengan setidaknya tiga simpul $|V'|\ge 3$ . Jadi, "grafik planar yang digeneralisasi" adalah yang memuaskan properti ini, dan mengenalinya dalam waktu polinomial tampaknya merupakan pertanyaan terbuka (menarik).

Dalam notasi Lee dan Streinu (rujukan di bawah) kelas kedua yang Anda daftarkan adalah grafik (2,3). Mereka memberikan algoritma untuk menguji apakah grafik (k, l) -parse dalam waktu polinomial. Namun, situasi dengan grafik planar dan sedikit lebih rumit, karena ketidaksetaraan itu tidak berlaku untuk semua set simpul (jika itu benar, tidak ada dua simpul yang dapat dihubungkan oleh tepi, karena ). Jadi kelas grafik (3,6) -sparse (dalam notasi mereka) hanya terdiri dari grafik kosong. Mungkin algoritma mereka dapat diperluas ke grafik dimana ketidaksamaan berlaku untuk semua set lebih dari dua simpul.$|E'|\le 3|V'|-6$$3\cdot 2-6=0$

Lee, Audrey; Streinu, Ileana (2008), "Algoritma permainan kerikil dan grafik jarang", Discrete Mathematics 308 (8): 1425–1437, doi: 10.1016 / j.disc.2007.07.104 , arxiv: math / 0702129 .

Apa yang diketahui tentang "grafik outerplanar umum" atau (2,3)-grafik kasar? Beberapa fakta tambahan untuk jawaban David Eppstein:

Pada tahun 1982, dalam makalah ini (Corollaries 1 dan 2), Lovász dan Yemini mengkarakterisasi grafik outerplanar yang digeneralisasi (dalam notasinya, grafik independen generik ) karena grafik memiliki properti yang menggandakan setiap tepi G menghasilkan grafik yang merupakan edge -menyatukan serikat dua hutan.$G$$G$

Sebelumnya, pada tahun 1970, Henneberg dan Laman membuktikan bahwa grafik outerplanar yang digeneralisasi dapat diperoleh secara rekursif dari oleh tiga yang disebut gerakan Henneberg (menambahkan simpul derajat-1, menambahkan simpul derajat-2, dan menambahkan semacam simpul tertentu). Gelar-3 vertex).$K_2$

Karakterisasi ini memberikan pengakuan polinomial pertama untuk grafik outerplanar umum.

Beberapa komentar yang berkaitan dengan grafik planar umum dapat ditemukan di bagian terakhir dari makalah ini . Saya pikir, mengkarakterisasi dan mengenali grafik planar umum masih menjadi pertanyaan terbuka yang sangat menarik.