2009
Approximating the Crossing Number of Apex Graphs
HLINĚNÝ, Petr, Markus CHIMANI a Petra MUTZELZákladní údaje
Originální název
Approximating the Crossing Number of Apex Graphs
Název česky
Aproximace průsečíkového čísla apexových grafů
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant, domácí), Markus CHIMANI (276 Německo) a Petra MUTZEL (276 Německo)
Vydání
5417. vyd. Berlin, Symposium Graph Drawing 2008, Lecture Notes in Computer Science, od s. 432-434, 3 s. 2009
Nakladatel
Springer Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Řecko
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Odkazy
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/09:00065851
Organizační jednotka
Fakulta informatiky
ISBN
978-3-642-00218-2
ISSN
UT WoS
000264579700041
Klíčová slova anglicky
crossing number; crossing minimization; apex graph
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 30. 4. 2014 05:53, RNDr. Pavel Šmerk, Ph.D.
V originále
We show that the crossing number of an apex graph, i.e.\ a graph $G$ from which only one vertex $v$ has to be removed to make it planar, can be approximated up to a factor of $\Delta(G-v)\cdot d(v)/2$ by solving the \emph{vertex inserting} problem, i.e.\ inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Due to a recently developed polynomial algorithm for the latter problem, this establishes the first polynomial fixed-constant approximation algorithm for the crossing number problem of apex graphs with bounded degree.
Česky
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.
Návaznosti
| GA201/08/0308, projekt VaV |
| ||
| MSM0021622419, záměr |
| ||
| 1M0545, projekt VaV |
|