Menemukan dual grafik

Menurut buku Teori Topologi Grafik oleh Gross dan Tucker, diberikan embedding seluler grafik pada suatu permukaan (dengan 'permukaan' yang saya maksudkan adalah bola dengan beberapa pegangan, dan di bawah S n mengacu pada bola dengan tepat n handle), seseorang dapat mendefinisikan multigraf ganda dengan memperlakukan wajah dari grafik asli yang disematkan sebagai simpul dan menambahkan tepi antara dua simpul untuk setiap sisi yang memiliki kesamaan pada grafik asli.$n\geq 0$$S_n$$n$

Inilah masalah saya . Diberikan grafik , saya perlu menemukan grafik G ′ sedemikian rupa sehingga ada permukaan S dan seluler yang menyematkan G pada S sehingga G ′ adalah ganda dari penyematan G ini . Saya tahu bahwa ada banyak kemungkinan grafik G ′ ; Aku hanya perlu menemukan satu untuk setiap graf G .$G$$G'$$S$$G$$S$$G'$$G$$G'$$G$

Saya punya beberapa pertanyaan . Strategi saya saat ini adalah untuk (1) menentukan genus dari G , (2) menemukan embedding G pada S n , dan (3) menemukan ganda embedding ini. Semua langkah tersebut memiliki algoritma yang diketahui (meskipun (1) adalah NP-Hard). Saya bertanya-tanya apakah ada cara untuk menemukan G ′ yang melewati perhitungan genus, karena itu adalah hambatan dari pendekatan ini, dan itulah pertanyaan pertama saya. Pertanyaan kedua saya adalah: Jika saya tahu bahwa G itu teratur, dapatkah itu memudahkan perhitungan genus? Dan pertanyaan ketiga saya adalah permintaan untuk referensi yang dapat membantu saya memecahkan masalah ini.$n$$G$$G$$S_n$$G'$$G$

Apakah dual Anda harus genus minimum? Karena itu sepele untuk menemukan embedding seluler untuk grafik apa pun: cukup pilih urutan melingkar untuk insiden tepi ke setiap verteks, secara sewenang-wenang, dan kemudian tentukan wajah embedding sebagai urutan tepi yang konsisten dengan urutan yang dipilih.

Saya suka representasi GEM (graph-encoded map) dari embedding dari buku Foundations of Topological Graph Theory oleh Bennington and Little. Dalam representasi ini, embedding diwakili oleh grafik 3-warna 3-tepi berwarna dengan satu simpul untuk setiap bendera embedding (insiden tiga simpul, tepi, dan wajah) dan satu tepi untuk setiap dua bendera yang berbeda dalam hanya satu dari elemen set simpul / tepi / wajah yang mereka wakili. Sebagai contoh, gambar di bawah ini dari Wikipedia dapat diartikan sebagai GEM dari dodecahedron biasa, di mana siklus merah mewakili wajahnya, siklus kuning mewakili tepinya, dan siklus biru mewakili simpulnya; ujung-ujungnya dapat diwarnai sesuai dengan warna dari dua wajah yang terjadi.

Diberikan urutan melingkar pada tepi grafik G, GEM-nya dapat ditemukan dengan membuat siklus simpul 2d untuk setiap derajat-d simpul G, dua untuk setiap tepi, dengan pasangan simpul untuk setiap tepi kejadian yang terjadi di siklus dalam urutan melingkar yang dipilih, dan kemudian untuk setiap tepi e dari G menghubungkan dua pasang tepi GEM untuk dua titik akhir dari e ke dalam persegi panjang. Jika Anda menginginkan penyematan berorientasi pilihan bagaimana menghubungkan keempat simpul ini ke dalam persegi panjang harus konsisten dengan urutan melingkar, jika tidak maka bisa sewenang-wenang.

Kemudian, simpul, tepi, dan wajah dari embedding G diwakili oleh siklus dalam GEM yang bergantian antara dua dari tiga warna tepi. Dual G diwakili oleh GEM dengan grafik 3-reguler yang mendasari yang sama tetapi dengan dua warna tepi yang ditukar. Dan grafik yang diwakili oleh GEM dapat dibentuk dengan mengontrak semua siklus verteksnya dan menggabungkan pasangan tepi paralel menjadi tepi tunggal. Jadi, membangun dual G (selama Anda tidak peduli dual mana) dapat dengan mudah dilakukan dalam waktu linier.