wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

planar_graph (846B)

      1 # Planar graph
      2 
      3 A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [plane_mathematics]
      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 
     12 [Theorems]:
     13 
     14 - [Kuratowskis_theorem] in terms of [topological_minors]
     15 - [Wagners_theorem] in terms of [graph_minors]
     16 
     17 Necessary conditions:
     18 
     19 - [Euler's_formula]
     20   - implies that [average_degree] must be at most 6
     21 
     22 Specific algorithms:
     23 
     24 - [fkt_algorithm]
     25 
     26 Generalizations:
     27 
     28 - to [hypergraphs]: [planar_hypergraph]
     29 - to [directed_graphs]: [directed_planar_graph]
     30 - to quantify the "degree of non-planarity": [crossing_number]
     31 
     32 See also: [graph_drawing]
     33 
     34 Up: [graph]
     35 
     36 Aliases: planar graphs, planar, graph planar, graphs planar