NAME
Graph::Maker::TwinAlternateAreaTree  create twin alternate area tree graph
SYNOPSIS
use Graph::Maker::TwinAlternateAreaTree;
$graph = Graph::Maker>new ('twin_alternate_area_tree', level => 6);
DESCRIPTION
Graph::Maker::TwinAlternateAreaTree
creates a Graph.pm
graph of a twin alternate area tree.
6362 5958 4746 4342
     
6160 5756 4544 4140
  
5554 5150 3938 3534
     
5352 4948 3736 3332

3130 2726 1514 1110
     
2928 2524 1312 98 level => 6
  
2322 1918 76 32
     
2120 1716 54 10
Graph vertices are unit squares inside a twin alternate curve formed by two alternate paperfolding curves backtoback, or equivalently a cycle of four such curves. For level=k the twin alternate is four level k paperfolding curves. It has 2^k squares inside which are vertices. Edges are between squares with segments consecutive in the curve. Or equivalently if the curves are drawn with corners chamfered off to leave little gaps at corners then edges connect squares through those gaps. See the author's mathematical writeup for more
Vertices are numbered 0 to 2^level1. These are Zorder point numbers corresponding to the unit squares in the twin alternate. The layout above is YX + Y*i, so Y coordinate unchanged and horizontally YX shear and negate.
With this vertex numbering, edges are between bit patterns
xxx0  xxx1 horizontal, toggle low bit
xxx 11 00..00
\/ vertical, toggle low run + 2
 when respective bit pattern
/\
xxx 00 11..11
Level=0 is a single vertex 0 and no edges.
Level=1 is two vertices 0 and 1 and an edge between them by the horizontal toggle low bit rule.
01 level => 1
Level=2 has the vertical rule connecting vertices 0 = 00 binary and 3 = 11 binary. These are 11 with no trailing 0s, connected to 00 with no trailing 1s.
32
 level => 2
10
Level=3 is also still a path. Its middle vertical is 1 = 001 connected to 6 = 110 so a low run of one bit before the 00  11.
76 32
   level => 3
54 10
Level=4 is the first not simply a path. The new edge is 3 = binary 0011 up to 12 = binary 1100.
1514 1110
  
1312 98 level => 4

76 32
  
54 10
Vertices are degree 1, 2 or 3. Vertex 0 can be considered as the root. Level k+1 is formed by taking level k and extending with a second copy of level k connected by a middle edge. This is between bit patterns 0011..11 in the first copy and 1100..00 in the second, per the level=4 above. In the big level=6 example above this is vertices 15 to 48.
Each level is the previous plus a copy of that previous attached at the biggest bit pattern edge. The effect is to make two spines continuing infinitely.
vertical spine 0,3,12,15,...
North West stairstep spine 0,1, 6, 7,24,...
The vertical spine and the vertices branching off from it are N with an even length in binary. The NW spine and the vertices branching off from it are N with an odd length in binary.
FUNCTIONS
$graph = Graph::Maker>new('twin_alternate_area_tree', key => value, ...)

The key/value parameters are
level => integer >= 0 graph_maker => subr(key=>value) constructor, default Graph>new
Other parameters are passed to the constructor, either
graph_maker
orGraph>new()
.Like
Graph::Maker::BalancedTree
, if the graph is directed (the default) then edges are added in both directions between nodes. Optionundirected => 1
creates an undirected graph and for it there is a single edge between vertices.
HOUSE OF GRAPHS
House of Graphs entries for the trees here include
1310 level=0, singleton
19655 level=1, path2
594 level=2, path4
260 level=3, path8
27042 level=4
27044 level=5
27046 level=6
33541 level=7
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include
http://oeis.org/A053599 (etc)
A053599 diameter of level
A077866 height of level
A001196 vertices of vertical spine
A053754 vertices of vertical spine and branches from it,
being N binary even length
A053738 vertices of NW spine and branches from it,
being N binary odd length
SEE ALSO
Graph::Maker, Graph::Maker::TwindragonAreaTree, Graph::Maker::BalancedTree
Math::PlanePath::AlternatePaper
LICENSE
Copyright 2017, 2018, 2019 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.