Niech G będzie niepustym grafem prostym. Graf, który można przedstawić na płaszczyźnie w taki sposób, że żadne dwie krawędzie nie przecinają się nazywamy grafem płaskim, natomiast graf nazywamy planarnym, gdy jest on izomorficzny do grafu płaskiego. Jeśli dodatkowo wszystkie jego wierzchołki leżą na obszarze zewnętrznym, graf nazywamy zewnętrznie planarnym. Indeksem krawędziowym grafu G nazywamy najmniejsze k takie, że k-ty iterowany graf krawędziowy grafu G jest nieplanarny. Analogicznie definiujemy indeks krawędziowo-blokowy, zewnętrznie-krawędziowy i zewnętrznie-krawędziowo-blokowy. W artykule charakteryzujemy wszystkie grafy pod względem wartości powyższych indeksów.
Authors
Additional information
- Category
- Publikacja monograficzna
- Type
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Language
- polski
- Publication year
- 2009
Source: MOSTWiedzy.pl - publication "Planarność i zewnętrzna planarność grafów" link open in new tab
