Informacje o właściwościach macierzy sąsiedztwa, gdy wykres jest płaski

21

1- Czy są jakieś szczególne właściwości macierzy przylegania, gdy wykres jest płaski?
2- Czy jest coś specjalnego do obliczania stałej macierzy przylegania, gdy wykres jest płaski?

marjoonjan
źródło
8
Przed napisaniem pytań przeprowadź przynajmniej kontrolę pisowni. To nie jest palanr, to jest planarne
Suresh Venkat,
:)) OK Jasne, obiecuję zrobić! :)
marjoonjan,
A co z dwustronnym wykresem planarnym?
Mohammad Al-Turkistany,
Osobiście nie dbam o dwuczęściowy wykres planarny, ale jeśli coś jest w twoim umyśle, to jest mile widziane! podziel się nim, proszę!
marjoonjan,
Czy obliczenie dwustronnego grafu płaskiego jest trwałe?
T ....

Odpowiedzi:

25

Obliczanie wyznaczników i stałych grafów płaskich jest tak trudne, jak obliczanie ich na grafach ogólnych. Są kompletne odpowiednio dla GapL i #P . Zobacz ten artykuł Datty, Kulkarni, Limaye, Mahajan, aby uzyskać więcej informacji.

Shiva Kintali
źródło
Czy obliczenie dwustronnego grafu płaskiego jest trwałe?
T ....
@Arul Tak, według algorytmu FKT en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
15

Jest to bardziej właściwość macierzy padania niż macierzy przylegania, ale jedną ważną właściwością grafów płaskich jest to, że są to dokładnie wykresy, których matroid graficzny jest podwójny z innym matroidem graficznym. Związek z macierzami padania polega na tym, że matroid graficzny opisuje zestawy niezależnych kolumn w macierzy.

David Eppstein
źródło
9

Istnieje właściwość macierzy odległości (a nie macierzy przylegania) ograniczonych grafów płaskich, która może być interesująca, właściwość Monge . Właściwość Monge (z powodu Gaspard Monge) dla grafów płaskich zasadniczo oznacza, że niektóre najkrótsze ścieżki nie mogą się przeciąć. Zobacz Wikipedia: Monge Array, aby uzyskać formalny opis właściwości Monge. Djidjev (WG 1996) ( artykuł na stronie internetowej Dżidżiwa ) oraz Fakcharoenphol i Rao (FOCS 2001) ( wideo ) pokazują, jak wykorzystać właściwości nieprzekraczania w algorytmach najkrótszej ścieżki.

Christian Sommer
źródło
6

Nie jestem pewien, jakiego rodzaju właściwości szukasz, ale promień spektralny grafów płaskich jest jedną z takich wielkości (maksymalna wartość bezwzględna wartości własnej macierzy sąsiedniej). Zobacz na przykład ten artykuł .

Suresh Venkat
źródło
6

Chociaż nie jest to bezpośrednio związane z twoim pytaniem, możesz przyjrzeć się pracy nad sekwencjami stopni grafów płaskich. Nie są znane charakterystyki, kiedy sekwencją stopni jest sekwencja stopni na wykresie planarnym. Istnieje jednak wiele interesujących artykułów na takie tematy, w tym:

http://www.jstor.org/pss/2100346

Joseph Malkevitch
źródło