class_docstr: A class to maintain the state during planarity check.
class_docstr_tok: ["A","class","to","maintain","the","state","during","planarity","check","."]
docstr: Execute the LR planarity test.
  
  Returns
  -------
  embedding : dict
      If the graph is planar an embedding is returned. Otherwise None.
docstr_tok: ["Execute","the","LR","planarity","test",".","Returns","--","--","--","-","embedding",":","dict","If","the","graph","is","planar","an","embedding","is","returned",".","Otherwise","None","."]
code: def lr_planarity(self):
      """Execute the LR planarity test.
  
      Returns
      -------
      embedding : dict
          If the graph is planar an embedding is returned. Otherwise None.
      """
      if self.G.order() > 2 and self.G.size() > 3 * self.G.order() - 6:
          # graph is not planar
          return None
  
      # make adjacency lists for dfs
      for v in self.G:
          self.adjs[v] = list(self.G[v])
  
      # orientation of the graph by depth first search traversal
      for v in self.G:
          if self.height[v] is None:
              self.height[v] = 0
              self.roots.append(v)
              self.dfs_orientation(v)
  
      # Free no longer used variables
      self.G = None
      self.lowpt2 = None
      self.adjs = None
  
      # testing
      for v in self.DG:  # sort the adjacency lists by nesting depth
          # note: this sorting leads to non linear time
          self.ordered_adjs[v] = sorted(
              self.DG[v], key=lambda x: self.nesting_depth[(v, x)]
          )
      for v in self.roots:
          if not self.dfs_testing(v):
              return None
  
      # Free no longer used variables
      self.height = None
      self.lowpt = None
      self.S = None
      self.stack_bottom = None
      self.lowpt_edge = None
  
      for e in self.DG.edges:
          self.nesting_depth[e] = self.sign(e) * self.nesting_depth[e]
  
      self.embedding.add_nodes_from(self.DG.nodes)
      for v in self.DG:
          # sort the adjacency lists again
          self.ordered_adjs[v] = sorted(
              self.DG[v], key=lambda x: self.nesting_depth[(v, x)]
          )
          # initialize the embedding
          previous_node = None
          for w in self.ordered_adjs[v]:
              self.embedding.add_half_edge(v, w, ccw=previous_node)
              previous_node = w
  
      # Free no longer used variables
      self.DG = None
      self.nesting_depth = None
      self.ref = None
  
      # compute the complete embedding
      for v in self.roots:
          self.dfs_embedding(v)
  
      # Free no longer used variables
      self.roots = None
      self.parent_edge = None
      self.ordered_adjs = None
      self.left_ref = None
      self.right_ref = None
      self.side = None
  
      return self.embedding
  
imports: from collections import defaultdict
  import networkx
label_desc: Use image node_id 2 for calling the LRPlanarity obj's underlying member method code with example usage: obj.lr_planarity() and returns: self, None, None