2012
Vertex insertion approximates the crossing number of apex graphs
HLINĚNÝ, Petr, Markus CHIMANI a Petra MUTZELZákladní údaje
Originální název
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
HLINĚNÝ, Petr (203 Česká republika, garant, domácí), Markus CHIMANI (276 Německo) a Petra MUTZEL (276 Německo)
Vydání
European Journal of Combinatorics, Elsevier, 2012, 0195-6698
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.658
Kód RIV
RIV/00216224:14330/12:00057323
Organizační jednotka
Fakulta informatiky
UT WoS
000299858000005
Klíčová slova anglicky
crossing number; crossing minimization; apex graph
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 19. 4. 2013 11:10, 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
| GEGIG/11/E023, projekt VaV |
|