Penempelan kombinasi grafik

12

Di sini: http://www.planarity.org/Klein_elementary_graph_theory.pdf (dalam bab embeddings) diberi definisi embedding kombinatorial dari grafik planar. (dengan definisi wajah dan sebagainya) Meskipun dapat dengan mudah digunakan untuk grafik apa pun, mereka mendefinisikan grafik planar sebagai grafik, yang dipegang oleh rumus Euler (dengan asumsi bahwa grafik terhubung). Cukup dapat dimengerti bahwa untuk setiap grafik bidang , definisi wajah dalam penanaman kombinatorial mirip dengan definisi wajah dalam penanaman topologi. (dengan asumsi grafik terhubung. Kalau tidak, dalam embedding kombinatorial kita akan memiliki wajah tanpa batas untuk setiap komponen yang terhubung)

Pertanyaannya adalah: jika untuk beberapa graf yang terhubung, penyertaan kombinatorial memenuhi rumus Euler, apakah ini berarti bahwa grafik ini adalah planar dalam arti topologis (memiliki penyematan bidang, yaitu grafik bidang )?

graph-theory co.combinatorics planar-graphs Finsky
sumber
Kemudian dalam makalah ini mereka memberikan jawaban bahwa ini mungkin. Tetapi adakah yang bisa memberikan tautan ke buktinya?
Finsky

Jawaban:

16

Ini benar-benar kurang tentang grafik per se dan lebih banyak tentang topologi. Embedding kombinatorial mendefinisikan 2-manifold, ruang topologi di mana setiap titik memiliki lingkungan homeomorfik ke disk terbuka 2-dimensi: penanaman memungkinkan wajah untuk didefinisikan, dan kita dapat mendefinisikan ruang topologis dengan memilih disk untuk masing-masing hadapi dan tempelkan bersama di sepanjang tepi grafik. Teorema terkenal dalam topologi (disebut klasifikasi 2-manifold) memberi tahu kita dengan tepat 2-manifold mana yang mungkin, dan mereka semua dapat dibedakan satu sama lain baik oleh apakah mereka berorientasi atau apakah mereka memiliki karakteristik Euler yang sama (atau keduanya ) - lihat http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdfuntuk beberapa catatan kuliah yang masuk akal tentang hal ini, itu termasuk bukti yang Anda minta. Tidak ada manifol 2 lainnya dalam klasifikasi ini yang memiliki karakteristik Euler yang sama dengan bola, jadi jika Anda menghitung karakteristik Euler dan menemukan bahwa itu cocok dengan rumus untuk bola, Anda tahu penyematan Anda harus ke bola.

Menemukan embedding dengan koordinat geometris yang sebenarnya di pesawat, setelah Anda memiliki embedding kombinatorial planar, tidak sepenuhnya sepele tetapi dapat dilakukan misalnya menggunakan teori hutan Schnyder. Saya punya beberapa catatan kuliah tentang ini di http://www.ics.uci.edu/~eppstein/gina/schnyder/ misalnya.

David Eppstein
sumber
Terima kasih banyak atas jawaban yang begitu luas! Saya sudah membaca makalah pertama dan sepertinya saya mengerti buktinya. Tapi saya punya satu pertanyaan lagi: apakah ini semua berarti bahwa jika kita akan menentukan permukaan apa pun yang kita suka (maksud saya adalah beberapa subset tepi yang sewenang-wenang, tidak seperti dalam kombinasi kombinatorial dengan urutan dan barang berlawanan arah jarum jam), tempelkan semuanya dengan cara sedemikian rupa sehingga lem hanya pada berbagi tepi 2 permukaan, tentukan 'simpul' yang dihasilkan pada titik akhir tepi sebagai simpul DAN jika rumus Euler berlaku, apakah ini grafik planar?
Finsky
1
Anda harus berhati-hati bahwa Anda mendapatkan manifold: wajah dari embedding harus disk topologi, Anda tidak boleh meninggalkan tepi yang unglued, setiap tepi hanya boleh dilem ke tepi lainnya, dan pada setiap titik hanya ada satu siklus tepi dan wajah terpaku di sekitarnya (tidak seperti apa yang Anda dapatkan jika Anda merekatkan dua kerucut di ujungnya). Anda juga harus mulai dengan grafik yang terhubung, atau menghitung karakteristik Euler untuk setiap komponen secara terpisah. Tetapi jika semua itu benar, dan formula Euler berlaku, maka ya, itu planar.
David Eppstein
Ya, lupa tentang kasus-kasus itu, tentu mereka harus memegang juga. Terima kasih banyak!
Finsky