planar_graph (1106B)
1 # Planar graph 2 3 A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [plane_mathematics], without [edges] that cross 4 5 - Recognizing them: [planarity_testing] 6 - [dynamic_planarity_testing] 7 - [carving_width] efficient computation: 8 - [seymour1994call] "rat-catcher" "ratcatcher" 9 - open for [treewidth] 10 - [planar_language] 11 - [hendrey2025optimal]: in an optimum-width [tree_decomposition] of a planar graph, the bags can be themselves assumed to have treewidth 3 12 13 [Theorems]: 14 15 - [Kuratowskis_theorem] in terms of [topological_minors] 16 - [Wagners_theorem] in terms of [graph_minors] 17 18 Necessary conditions: 19 20 - [Euler's_formula] 21 - implies that [average_degree] must be at most 6 22 23 Specific algorithms: 24 25 - [fkt_algorithm] 26 27 Special cases: 28 29 - [graph_outerplanar] 30 31 Generalizations: 32 33 - to [hypergraphs]: [planar_hypergraph] 34 - to [directed_graphs]: [directed_planar_graph] 35 - to quantify the "degree of non-planarity": [crossing_number] 36 - [single_crossing_graph] 37 38 See also: [graph_drawing], [planar_separator_theorem] 39 40 Up: [graph] 41 42 Aliases: planar graphs, planar, graph planar, graphs planar