Advanced Search

Question: Is there an efficient way to test whether a graph is maximal outerplanar?

Question:Is there an efficient way to test whether a graph is maximal outerplanar?

lcz 994
programming graphtheory
March 25 2021
1

I asked before how to determine whether a graph is  outerplanar graph.  vv  and  Carl Love  provided very good guidance. 

https://www.mapleprimes.com/questions/229128--How-To-Determine-If-A-Graph-Is-Outerplanar

 Today I tried to use the previous code to further determine whether a plane graph is maximal outerplanar graph.

A maximal outerplanar graph is an outerplanar graph that cannot have any additional edges added to it while preserving outerplanarity.

IsOuterplanar:= proc(G::Graph)
uses GT= GraphTheory;
    GT:-IsPlanar(GT:-GraphJoin(G, GT:-PathGraph(1)))
end proc:
IsmaximalOuterplanar:= proc(G::Graph)
uses GT= GraphTheory:
local glist, Outerplanartest:
      glist:= map[2](GT:-AddEdge,G,GT:-Edges(GT:-GraphComplement(G)),inplace = false ):
       Outerplanartest:=IsOuterplanar~(glist):
      if evalb(true in Outerplanartest) then  
         return false:
       else
         return true:
      fi:
end proc:

I feel that the  above adding edges in programs is a bit inefficient.

So I wonder if there is a better way.  Then I want to start from property of this graph class.

Some Properties:

  1. Every maximal outerplanar graph with n vertices has exactly 2n − 3 edges.
  2. A graph on  n (>=3) vertices  is  maximal outerplanar graph  if and if  every bounded face of a maximal outerplanar graph is a triangle and boundary of  unbounded face  is  Hamiltonian cycle. 

I noticed the second one. I don’t know if it can be achieved through programming. 

I want to get some information about the degree sequence of the face with the help of the dual graph . But I know  dual graph not unique   since  there are different plane embeddings  for not 3 connected  planar graphs. 

Or is there a more efficient way？

 

 
Please Wait...