How to find those missing edges in a grid graph

I want to find a new method for this question.Suppose I have a such graph

graph = Graph[{1 <-> 2, 1 <-> 6, 2 <-> 3, 2 <-> 7, 3 <-> 4, 3 <-> 17, 
   4 <-> 5, 4 <-> 9, 5 <-> 10, 6 <-> 7, 7 <-> 17, 7 <-> 12, 17 <-> 9, 
   17 <-> 13, 9 <-> 10, 9 <-> 14, 11 <-> 12, 11 <-> 16, 12 <-> 13, 
   12 <-> 8, 13 <-> 14, 13 <-> 18, 14 <-> 24, 14 <-> 19, 24 <-> 20, 

   16 <-> 8, 16 <-> 21, 8 <-> 18, 8 <-> 22, 18 <-> 19, 18 <-> 23, 
   19 <-> 20, 19 <-> 15, 20 <-> 25, 21 <-> 22, 21 <-> 26, 22 <-> 23, 
   22 <-> 27, 23 <-> 15, 23 <-> 28, 15 <-> 29, 25 <-> 30, 26 <-> 27, 
   27 <-> 28, 28 <-> 29, 29 <-> 30}, VertexLabels -> "Name"]

How to find those missing edges,such as {6<->11,10<->24,15<->25}?

Answer

If only edges are missing, you can first generate a list of candidate grid graphs with the same number of nodes as in graph, then see which one contains graph as a subgraph. IGraph/M has subgraph finding functionality.

It could be derived from any of these grids, as they all have the same number of nodes:

candidateGrids =
 With[{vc = VertexCount[graph]},
  GridGraph[{#, vc/#}] & /@ Select[Divisors[vc], # <= Sqrt[vc] &]
 ]

Select the first one of these which contains graph as a subgraph:

<< IGraphM`
completeGrid = SelectFirst[candidateGrids, IGSubisomorphicQ[graph, #] &]

We can find one mapping between the vertices of graph and completeGrid using IGVF2GetSubisomorphism:

mapping = First@IGVF2GetSubisomorphism[graph, completeGrid]
(* <|1 -> 1, 2 -> 2, 6 -> 6, 3 -> 3, 7 -> 7, 4 -> 4, 17 -> 8, 
 5 -> 5, 9 -> 9, 10 -> 10, 12 -> 12, 13 -> 13, 14 -> 14, 11 -> 11, 
 16 -> 16, 8 -> 17, 18 -> 18, 24 -> 15, 19 -> 19, 20 -> 20, 21 -> 21, 
 22 -> 22, 23 -> 23, 15 -> 24, 25 -> 25, 26 -> 26, 27 -> 27, 28 -> 28,
  29 -> 29, 30 -> 30|> *)

Then you can retrieve whatever you like: vertex coordinates, missing edges, etc.

coords = PropertyValue[{completeGrid, #}, VertexCoordinates] & /@ 

  Lookup[mapping, VertexList[graph]]

SetProperty[
 graph,
 VertexCoordinates -> Thread[VertexList[graph] -> coords]
]

Or missing edges:

reverseMapping = Reverse /@ Normal[mapping];


missing =
 Block[{UndirectedEdge},
  SetAttributes[UndirectedEdge, Orderless];
  Complement[
   EdgeList[completeGrid] /. reverseMapping,
   EdgeList[graph]
   ]
  ]
(* {6 <-> 11, 10 <-> 24, 15 <-> 25} *)

(The Orderless attribute is temporarily set on UndirectedEdge to make sure that a <-> b is considered the same as b <-> a.)

HighlightGraph[
 VertexReplace[completeGrid, reverseMapping],
 missing,
 GraphHighlightStyle -> "Dashed",
 Options[completeGrid, GraphLayout]
 ]

---

This will, of course, be quite slow due to the difficulty of finding subgraphs. It will only work well for small grids like the one in your example.

To get all possible mappings instead of just one, use IGVF2FindSubisomorphisms. There will always be at least 4 possible mapping due to the symmetries of grid graphs.