2022/07/13 by Joel Foisy, Foisy, Joel
Computer Science · Social Sciences · #05C10 #05C22 #57K10 #57M15 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Cross-Border Cooperation and Integration #FOS: Mathematics #Geometric Topology (math.GT)
paper · pdf · doi:10.48550/arxiv.2207.06244
openalex publication_date 2022/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Tutte showed that a graph G is planar if and only if the conflict graph associated to every cycle of G is bipartite. We define a (not necessarily unique) signed conflict graph associated to a maximally planar subgraph of a nonplanar graph such that if G has a flat embedding, every possible conflict graph associated to every maximally planar subgraph of G is balanced. In doing this, we show that for every graph G with flat embedding, and a planar subgraph P of G, P lies on a sphere that intersects G only in P. We conjecture that G is intrinsically linked if and only if every maximal planar subgraph of G has every possible conflict graph unbalanced.