Informace o publikaci
Vertex insertion approximates the crossing number of apex graphs
| Název česky | Vložení vrcholu aproximuje průsečíkové číslo apexových grafů |
|---|---|
| Autoři | |
| Rok publikování | 2012 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Fakulta / Pracoviště MU | |
| 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: |