Vertex insertion approximates the crossing number of apex graphs

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Vložení vrcholu aproximuje průsečíkové číslo apexových grafů
Autoři

HLINĚNÝ Petr CHIMANI Markus MUTZEL Petra

Rok publikování 2012
Druh Článek v odborném periodiku
Časopis / Zdroj European Journal of Combinatorics
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1016/j.ejc.2011.09.009
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.