Informace o publikaci
Approximating the Crossing Number for Graphs close to "Planarity"
| Název česky | Aproximace průsečíkového čísla pro grafy "blízké rovinným" |
|---|---|
| Autoři | |
| Rok publikování | 2007 |
| Druh | Článek ve sborníku |
| Konference | Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Abstracts collection, Dagstuhl Seminar 07281 |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://drops.dagstuhl.de/portals/index.php?semnr=07281 |
| Obor | Informatika |
| Klíčová slova | graph; crossing number; almost planar |
| Popis | Ukazujeme, že průsečíkové číslo grafu lze aproximovat pro téměř planární, projektivní a toroidální grafy. Zároveň se ptáme, jak mnoho "nerovinnosti" grafu lze povolit, aby stále byl efektivní výpočet možný. |
| Související projekty: |