Approximating the Crossing Number of Apex Graphs

Logo poskytovatele

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 apexových grafů
Autoři

HLINĚNÝ Petr CHIMANI Markus MUTZEL Petra

Rok publikování 2009
Druh Článek ve sborníku
Konference Symposium Graph Drawing 2008, Lecture Notes in Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www conference
Doi http://dx.doi.org/10.1007/978-3-642-00219-9_42
Obor Informatika
Klíčová slova crossing number; crossing minimization; apex graph
Popis Dokážeme, že průsečíkové číslo grafu G, který se jedním vrcholem v liší od rovinného, je aproximovatelné s faktorem \Delta(G-v)\cdot d(v)/2 problémem vložení vrcholu v do rovinného nakreslení G.
Související projekty:

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