. . . "Approximating the Crossing Number of Apex Graphs" . "Berlin" . "crossing number; crossing minimization; apex graph"@en . "Approximating the Crossing Number of Apex Graphs"@en . "Chimani, Markus" . . "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." . "000264579700041" . "RIV/00216224:14330/09:00065851" . "Approximating the Crossing Number of Apex Graphs" . "P(1M0545), P(GA201/08/0308), S, Z(MSM0021622419)" . "2008-10-21+02:00"^^ . "14330" . "Springer-Verlag" . . . . . . "303919" . . . . . "0302-9743" . . . "Symposium Graph Drawing 2008, Lecture Notes in Computer Science" . "Heraklion, Greece" . "Mutzel, Petra" . "RIV/00216224:14330/09:00065851!RIV14-MSM-14330___" . "9783642002182" . "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."@en . . "http://www.gd2008.org/" . . "3"^^ . . "3"^^ . "1"^^ . "10.1007/978-3-642-00219-9_42" . . "Approximating the Crossing Number of Apex Graphs"@en . "[A35935C2C1BD]" . "Hlin\u011Bn\u00FD, Petr" . .