{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.00119127,0.001200248,0.001411475,0.0009152422,0.001520028,0.003724716,0.002756028,0.002525947,0.007593976],"category_scores_gemma":[0.011874,0.001496397,0.002078803,0.001877356,0.0031583,0.009729946,0.00394185,0.006701498,0.001150829],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001426356,"about_ca_system_score_gemma":0.001152771,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001287036,"about_ca_topic_score_gemma":0.001873087,"domain_scores_codex":[0.9978549,0.0003826412,0.000118033,0.0008226055,0.000473358,0.000348504],"domain_scores_gemma":[0.9809994,0.01435288,0.001291581,0.002179082,0.0006302303,0.000546944],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.001250339,0.0006425494,0.007276692,0.001713863,0.0002441998,0.001381965,0.0008652089,0.3788846,0.02645474,0.4116366,0.02991775,0.1397315],"study_design_scores_gemma":[0.0001536454,0.0001510904,0.001733275,0.00009973938,0.0001462634,0.001243296,0.0003749638,0.2044404,0.01333213,0.764908,0.01333807,0.00007914149],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.4953814,0.001202197,0.4453893,0.01012257,0.00029791,0.0002048302,0.001883349,0.001996172,0.04352232],"genre_scores_gemma":[0.8100084,0.001871037,0.173485,0.001132605,0.0003308014,0.0001865521,0.003231297,0.000498127,0.009256202],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.007593976,"threshold_uncertainty_score":0.02540445,"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."}}