![Důležité termíny](https://cdn.muni.cz/media/3633704/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
Approximating the Crossing Number of Apex Graphs
Název česky | Aproximace průsečíkového čísla apexových grafů |
---|---|
Autoři | |
Rok publikování | 2009 |
Druh | Článek ve sborníku |
Konference | Symposium Graph Drawing 2008, Lecture Notes in Computer Science |
Fakulta / Pracoviště MU | |
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: |