2013/11/26 by Marcus Schaefer, Schaefer, Marcus
Computer Science · Mathematics · #68R10 #Artificial Intelligence in Games #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematics and Applications #cs.CG #cs.DM #math.CO #msc:68R10
paper · pdf · doi:10.48550/arxiv.1311.6839
arxiv created 2013/11/26 · openalex publication_date 2013/11/26 · arxiv updated 2013/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G and a subset F ⊆ E(G) of its edges, is there a drawing of G in which all edges of F are free of crossings? We show that this question can be solved in polynomial time using a Hanani-Tutte style approach. If we require the drawing of G to be straight-line, and allow at most one crossing along each edge in F, the problem turns out to be as hard as the existential theory of the real numbers.