{"id":"W2004640854","doi":"10.1137/120872310","title":"Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard","year":2013,"lang":"en","type":"preprint","venue":"SIAM Journal on Computing","topic":"Computational Geometry and Mesh Generation","field":"Computer Science","cited_by":3,"is_retracted":false,"has_abstract":true,"ca_institutions":"","funders":"Natural Sciences and Engineering Research Council of Canada; Univerza v Ljubljani; Javna Agencija za Raziskovalno Dejavnost RS; European Science Foundation","keywords":"Book embedding; Planar graph; Crossing number (knot theory); Planarity testing; Combinatorics; Planar straight-line graph; Planar; Mathematics; 1-planar graph; Graph drawing; Outerplanar graph; Embedding; Polyhedral graph; Pathwidth; Graph; Discrete mathematics; Computer science; Line graph","routes":{"ca_aff":false,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":true},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow","scholarly_communication"],"consensus_categories":[],"category_scores_codex":[0.001188871,0.0003985334,0.0004939652,0.0004822917,0.001276831,0.004077335,0.0008364615,0.000213051,0.00002719181],"category_scores_gemma":[0.0001474517,0.0004058401,0.0001647607,0.0004266706,0.00005332349,0.0003631625,0.0008702753,0.001435044,0.0001017379],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.000151407,"about_ca_system_score_gemma":0.0002665838,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0000281244,"about_ca_topic_score_gemma":0.000003593143,"domain_scores_codex":[0.9970584,0.0002328852,0.000702868,0.0007801403,0.0006993256,0.0005263817],"domain_scores_gemma":[0.9979073,0.0003705203,0.0005345743,0.0004058573,0.0003485469,0.0004332206],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.00008494218,0.000442457,0.009172551,0.00044357,0.0005283327,0.0002553564,0.007212163,0.2572948,0.002100705,0.09909428,0.02362479,0.599746],"study_design_scores_gemma":[0.001824438,0.0005465937,0.1168185,0.005121585,0.0001044877,0.00258249,0.000160079,0.7186661,0.001525641,0.1266049,0.02309886,0.002946296],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.513966,0.0002329386,0.4809519,0.0013121,0.00244903,0.0002352492,0.000007192116,0.0001181773,0.0007274054],"genre_scores_gemma":[0.743589,0.00002107827,0.2536458,0.001285386,0.001309582,0.000004032121,0.00001430521,0.00002378322,0.0001071106],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.5967997,"threshold_uncertainty_score":0.9998394,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.04051022457043105,"score_gpt":0.2926810343826916,"score_spread":0.2521708098122605,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}