2
$\begingroup$

Can HRGs generate languages which equal or include the following graph languages:

  1. All (bipartite) graphs of bounded degree
  2. All (bipartite) planar graphs of bounded degree
  3. All (bipartite) planar graphs in a square grid (so that every vertex has 4 neighbors)
  4. A good language of expander graphs

The HRGs can potentially generate additional graphs outside of those languages or generate predictable additional vertices and edges that can be removed through post-processing. It would also be of interest whether node replacement (C-edNCE specifically) languages can generate these languages.

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.