Approximating the Crossing Number for Graphs close to "Planarity"

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Aproximace průsečíkového čísla pro grafy "blízké rovinným"
Autoři

HLINĚNÝ Petr

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

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.