wiki_research

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

planar_graph (913B)

      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 Special cases:
     27 
     28 - [graph_outerplanar]
     29 
     30 Generalizations:
     31 
     32 - to [hypergraphs]: [planar_hypergraph]
     33 - to [directed_graphs]: [directed_planar_graph]
     34 - to quantify the "degree of non-planarity": [crossing_number]
     35 
     36 See also: [graph_drawing], [planar_separator_theorem]
     37 
     38 Up: [graph]
     39 
     40 Aliases: planar graphs, planar, graph planar, graphs planar