| Identifikační kód | RIV/00216224:14330/12:00057323 |
|---|
| Název v anglickém jazyce | Vertex insertion approximates the crossing number of apex graphs |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2012 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646)
Markus Chimani (státní příslušnost: DE - Spolková republika Německo)
Petra Mutzel (státní příslušnost: DE - Spolková republika Německo) |
|---|
| Popis výsledku v anglickém jazyce | 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 forthe crossing number problem of apex graphs with bounded degree. |
|---|
| Klíčová slova oddělená středníkem | crossing number; crossing minimization; apex graph |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1016/j.ejc.2011.09.009 |
|---|