Nonplanar Graph

Definition / 定义

非平面图：一种图，无法在平面上画出且不出现边与边的交叉（允许边只在共同端点相交）。常见的判定思路与库拉托夫斯基定理相关：若图包含（作为细分）(K_5) 或 (K_{3,3})，则为非平面图。

Pronunciation / 发音

/ˌnɒnˈpleɪnər ɡrɑːf/ (BrE), /ˌnɑːnˈpleɪnər ɡræf/ (AmE)

Examples / 例句

A complete graph (K_5) is a nonplanar graph.
完全图 (K_5) 是一个非平面图。

Even after redrawing the network carefully, the graph remained nonplanar because it contains a subdivision of (K_{3,3}).
即使仔细重新绘制该网络，这个图仍然是非平面图，因为它包含 (K_{3,3}) 的一个细分。

Etymology / 词源

non-（否定前缀，“不、非”）+ planar（“平面的”，来自 plane “平面”）+ graph（“图”，源自希腊语 graph- “书写/描画”）。合起来字面意思就是“不能画在平面上（而不交叉）的图”。

Related Words / 相关词

• Planar Graph
• Embedding
• Kuratowski’s Theorem
• Homeomorphism
• Subdivision
• Complete Graph
• Bipartite Graph
• Graph Minor

Literary Works / 文学作品

• Diestel, **Graph Theory**（讨论平面性与非平面图的判定与结构）
• Bondy & Murty, **Introduction to Graph Theory**（介绍平面图/非平面图与经典反例）
• Harary, **Graph Theory**（包含平面性、(K_5)、(K_{3,3}) 等内容）
• Kuratowski, “Sur le problème des courbes gauches en topologie”（1930，提出与非平面图判定相关的经典定理）