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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.