[iblvvyso] 2D CFG

start with an undirected graph.  nodes may be of two types, nonterminal or terminal.

zoom in on a nonterminal node.  it expands into a graph fragment, a graph consisting of one or more internal nodes, some number of internal edges, and a collection of edges going to "the outside" corresponding to the edges of the nonterminal node before zooming in.  some of the internal nodes may themselves be nonterminal, permitting further zooming in.

terminal nodes do not expand.

nonterminal nodes have labels.  different nodes may have the same label.  all nodes with the same label have the same degree (not necessarily vice versa).  the degree is the number of outbound edges, edges connected to the outside.

(despite the term "outbound", all the edges of the graph are undirected.)

the graph is an instantiation of a grammar with some additional features.  a grammar rule has a nonterminal on the left hand side and one or more alternatives on the right hand side.  a rule corresponds to a nonterminal label.  a rule specifies a set of outbound edges, common to all alternatives of that rule.  the degree of the rule is its number of outbound edges, the cardinality of that set.

an alternative specifies a graph fragment.  a graph fragment is a collection of terminals and nonterminals (nodes), their internal connections (edges), and the edges going to the outside.  an alternative specifies the matching between its graph fragment's outbound edges and the outbound edges specified by the rule.  because all alternatives of a rule have the same set of outbound edges, one can freely swap one alternative for another, as would be expected for a context-free grammar.

terminals are single nodes with no restrictions on degree.  if you want to put a degree restriction on a single node, wrap it in a nonterminal.

standard grammar tasks: given a parse tree specifying which alternative was chosen for each nonterminal, draw the graph, corresponding to pretty printing.  given a graph expanded out to all terminals, find a parse tree, that is, find the boundaries of groups of nodes that can be un-zoomed to nonterminals.

even if the top-level unexpanded graph is planar, and all graph fragments inside nonterminals are planar, it is not necessarily the case that the graph remains planar when fully expanded to terminals.  the rotational ordering of outbound edges from a nonterminal needs to match the inbound edges of the outer graph.

given a planar graph instantiation of a grammar, transform it into a map of regions.  an edge corresponds to adjacency, but the lack of an edge does not force non-adjacency: if two nodes are not connected by an edge, their corresponding regions can be adjacent, or not.  this is a relaxation from standard convention.  perhaps mark the borders which correspond to actual edges.

terminal regions can have region constraints, for example, at least a given area, or able to fit a given shape within it.

perhaps nodes with edges looping back to themselves correspond to regions with internal holes.  haven't thought this through.  what goes in the holes?

restrict the map to a square grid: regions must be polyominos.  perhaps mark the borders which correspond to edges.  if two nodes are connected by more than one graph edge, the length of the border between their corresponding regions must be at least the number of graph edges between them.

same grammar tasks as above but on the square grid: pretty printing and parsing.  both of these seem considerably more difficult than conventional "1D" grammar tasks.  for pretty printing, perhaps the map has to fit within a given box.

if terminals specify letters to put inside squares (details to be specified), the grammar tasks even more closely resemble those of 1D grammars, organizing layout of letters into nonterminals.

motivation was hierarchical city layout, perhaps for a game.  adjacency conditions define districts or businesses which need to be directly connected for transporting goods between them.

perhaps some mechanism to specify forced non-adjacency, but I suspect this is complicated.

generalizing to directed graphs seems not too difficult.