caa a22 4500 445804408 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-009-9357-5 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9357-5 Crossing Number and Weighted Crossing Number ofNear-Planar Graphs [Elektronische Daten] [Sergio Cabello, Bojan Mohar] A nonplanar graph G is near-planar if it contains an edge e such that G−e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněný and Salazar (Graph Drawing GD'06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs. Springer Science+Business Media, LLC, 2009 Crossing number nationallicence Near-planar nationallicence Almost planar nationallicence Planar separation nationallicence Dual distance nationallicence Facial distance nationallicence NP-hardness nationallicence Cabello Sergio Department of Mathematics, FMF, University of Ljubljana, Ljubljana, Slovenia aut Mohar Bojan Department of Mathematics, Simon Fraser University, V5A 1S6, Burnaby, BC, Canada aut Algorithmica Springer-Verlag 60/3(2011-07-01), 484-504 0178-4617 60:3<484 2011 60 453 https://doi.org/10.1007/s00453-009-9357-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9357-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cabello Sergio Department of Mathematics, FMF, University of Ljubljana, Ljubljana, Slovenia aut NATIONALLICENCE 700 1- Mohar Bojan Department of Mathematics, Simon Fraser University, V5A 1S6, Burnaby, BC, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 484-504 0178-4617 60:3<484 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer