论文标题
Tutte冲突图的空间版本
A spatial version of Tutte's conflict graph
论文作者
论文摘要
Tutte表明，当且仅当与$ g $的每个周期相关的冲突图是两部分时，图$ g $是平面。我们定义了与非平面图的最大平面子图关联的（不一定是唯一的）签名的冲突图，以便如果$ g $具有平坦的嵌入，则与$ g $的每个最大平面子图相关联的每一个可能的冲突图是平衡的。在这样做时，我们表明，对于每个图形$ g $，带有平坦的嵌入，以及平面子图$ p $ $ g $，$ p $都位于一个仅在$ p $中与$ g $相交的球体。我们猜想$ g $在且仅当每个最大平面子图的$ g $都具有所有可能的冲突图不平衡时，才具有本质上的链接。
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.
