wiki_research

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

planarity_testing (397B)

      1 # Planarity testing
      2 
      3 https://en.wikipedia.org/wiki/Planarity_testing
      4 
      5 given an [undirected_graph] G, is G [planar_graph]?
      6 
      7 can be done in [linear_time]
      8 
      9 on [dynamic_data]:
     10 
     11 - if edges arrive but are not deleted, tight [inverse_ackermann] algorithm
     12 - if edges can be added and deleted,
     13   - [logarithmic] [lower_bounds]
     14   - [polylogarithmic] [algorithm]
     15 
     16 Up: [planar_graph], [computational_problem]