Compound Perfect Squared Squares (CPSSs) are squares dissected into smaller squares, all different integer sizes, but with a rectangular inclusion (or a dissected square) in the tiling. These squared squares are scarcer than SPSSs (with recent substitution methods, this is no longer the case; see CPSS orders 40+). A great deal of thought and ingenuity has gone into the devising of methods of construction of CPSSs. The order 24 CPSS by T.H. Willcocks was found many years ( published 1948) before computers were able to verify it was indeed the lowest order example of its kind. See Simple Perfect Squared Squares for a chronology of Perfect Squared Square discoveries.
Compound squared squares have often been created using methods called 'transforms'. There are many dozens of transforms and they are generally not computer assisted. A transform will often change one square tiling into another.
One method uses algebra to create a CPSS from existing simple squared rectangles by selecting a squared rectangle from the catalogue and designating one of the square elements as a rectangle of indeterminate width and height, then making the height and width of the squared rectangle equal (to make it square), and recalculating both the sizes of the squares and the sides of the included rectangle using elementary algebra. The solution will be unique and with luck another perfect squared rectangle may be found in the catalogue which is able to fit into the included rectangle without any repeated elements.
CPSSs can also be created by combining Simple Perfect Squared Rectangles (SPSRs) in a number of different ways. Two SPSRs of the same size with no elements in common can be combined to make CPSS. Two SPSRs of the same shape, scaled can be combined to make CPSS. Several SPSRs of different sizes and shapes, but satisfying certain relationships can be combined into CPSSs. A construction based on the Fibonacci sequence as element sizes has also been used to create CPSSs. Computers can be used to speed up some of these methods.
A computational approach is also possible where 2-connected planar graph embeddings are generated, then transformed into compound square tilings using electrical network analysis. These tilings are tested for CPSSs.
The author of this website, Stuart E. Anderson, has written a paper 'Compound Perfect Squared Squares of the Order Twenties' (2013). It is available from the Arxiv link. It gives some historical and technical detail on CPSS construction, including an extensive bibliography on the topic of squared squares. However this website provides a great many more dissection codes and illustrations, mainly because the website is not limited to the low-orders and to CPSSs in particular.
Every CPSS is one of at least 4 isomers. The included compound rectangle can be positioned in 4 different ways. If the rectangle is trivially compound (has a square equal to the height or width of the rectangle) then the rectangle can be positioned in 8 ways, if the rectangle is doubly or triply trivially compound it can be positioned in 16 and 32 ways, and so on. Other kinds of compound construction are also possible. In pdf's and drop down menus, isomer number is shown with square id and discoverer id. The first couple of dozen different isomer counts for which we have examples are 4, 7, 8, 11, 12, 16, 19, 20, 23, 24, 28, 31, 32, 35, 36, 39, 40, 47, 48, 56, 60, 63, 64, 68, 72, 76, 80, 88, 96. By combining SPSR and SPSS isomers with the known CPSS isomers up to 96, we can create further CPSSs with isomer counts such as 112, 128, 132, 144, 152, 160, 176, 184, 192, 196, 224, 248, 256, 264, 288, 304, 320, 368, 384, 448, 456, 480, 496, 512, 544, 552, 576, 672, 744, 768, 864, 896, 1024, 1088, 1152, 1216, 1344, 1472, 1536, 1632, 1728, 1792, 1984, 2048, 4096. An isomer count of 7 is produced when 2 rectangles overlap with a common element, higher odd numbers of isomers are the result of overlaps and other arrangements. Geoffrey Morley has shown an isomer count of 14 is possible if suitable SPSRs can be found to construct a particular CPSS, so the sequence given above is expected to contain a number of such gaps where additional terms could be inserted. A linked pdf gives examples of all known isomer counts up to 96.
- 1902 H.E. Dudeney published a puzzle called Lady Isabel's Casket that concerns the dissection of a square into different sized squares and a rectangle. According to David Singmaster 'Lady Isabel's Casket' appeared first in London Mag. 7 (Jan 1902) 584 and is the first published reference dealing with the dissection of a square into smaller different sized squares. It was also published in The Canterbury Puzzles in 1907.
- 1907-1914 S. Loyd published The Patch Quilt Puzzle. A square quilt made of 169 square patches of the same size is to be divided into the smallest number of square pieces by cutting along lattice lines. The answer, which is unique, is composed of 11 squares with sides 1,1,2,2,2,3,3,4,6,6,7 within a square of 13. It is neither perfect nor simple. Gardner states that this problem first appeared in 1907 in a puzzle magazine edited by Sam Loyd. David Singmaster lists it as first appearing in 1914 in Cyclopedia by Loyd but credits Loyd with publishing Our Puzzle Magazine in 1907 - 08. This puzzle also appeared in a publication by Henry Dudeney as Mrs Perkins Quilt. Problem 173 in Amusements in Mathematics. 1917
- 1939 R.P. Sprague published a solution to the problem of squaring the square. Sprague constructed his perfect solution using several copies of various sizes of Z. Moroń's Rectangle I (33x32), Rectangle II (65x47) and a third 12 order simple perfect rectangle and five other elemental squares to create an order 55, compound perfect squared square (CPSS) with side 4205.
- 1939 Minutes of A. Stone's lecture: "Squaring the Square". Announces Brooks's example with 39 elements, side 4639, but containing a perfect subrectangle. Minutes of the 203rd Meeting of the Trinity Mathematical Society (Cambridge) (13 Mar 1939). Minute Books, vol. III, pp. 244‑246.
- 1940 R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T.Tutte published 'The Dissection of Rectangles into Squares" (1st page only), referring to an empirically constructed order 26 CPSS, side 608, attributed to Tutte. In the same year A.H. Stone uses 2 order 13 SPSRs as R1, R2 to construct and publish a Moroń dissection CPSS of order 28, side 1015.
- 1946-48 C.J. Bouwkamp published a series of papers in which he discussed methods for constructing squared rectangles and perfect squared squares. He gave a bouwkampcode listing of the CPSS of order 39 with side 1813 discovered by, but not shown in the Brooks, Smith, Tutte and Stone 1940 paper.
- 1948 T.H.Willcocks, published his discovery of a CPSS side 175, of order 24 in the Fairy Chess Review. It held the record as the smallest known size and lowest order perfect squared square for the next thirty years, and was eventually found to be the smallest size and lowest order CPSS. He also published two new CPSS in order 27, with sides 867 and 849, and a new CPSS in order 28 with a side of 577.
- 1950 W.T. Tutte published 'Squaring the Square'. In this paper he described in more detail the general methods by which a square may be dissected into (smaller unequal non-overlapping) squares. A number of new CPSSs are given, including a compound perfect squared square of order 85, side 227807876, constructed from two rectangles produced using advanced rotor-stator theory, he mentions a perfect squared square of the 29th order and has reduced side 1424, the Bouwkampcode is misformed so this must be an error or misprint as only one order 29: 1424 SPSS (no CPSSs) exists and it has different elements. The two compound perfect squared squares of side 1015 order 28 and a third of order 28 and side 1073 are given. Compound perfect squared squares of order 39 are given one with side 1813 (by the Trinity Four) and one with side 4639 due to Brooks.
- 1951 T.H.Willcocks, published 'A note on some perfect squared squares', his account of the methods he used to construct CPSSs with small sizes. He included a number of new squared squares, these included his discovery of a new CPSS of order 26 with side 492, and 2 new CPSSs of order 27 with sides 872 and 890.
- 1963 P.J. Federico published 'note on some low-order perfect squared squares' a paper in which he provided a detailed account of CPSS construction methods. Federico gave a new general empirical method, by means of which 24 perfect squares of order below 29 were constructed. The CPSSs he gave in his paper included two new CPSSs of order 25, one with a side of 235 and the other with a side of 344, a new CPSS of order 26, with side 384, 7 new CPSSs of order 27 with sides 325, 408, 600, 618, 645, 648, and 825, and 11 new CPSSs of order 28 with sides 374, 714, 732, 741, 765, 765, 824, 1071, 1089, 1113 and 1137. Federico defined the term 'low order' to mean the squared squares below order 29, he stated "this limit was chosen to avoid too long a list", and he also noted "twenty-nine perfect squares of order 29 were collected without attempting to apply fully the methods to this and higher orders", but only gave one example of a particular order 29 CPSS, size 468, indicative of the methods being illustrated in the list at the end of the paper. However in the paper itself he indicated how 7 new order 29 CPSSs were found, and gave sufficient information to work out their sizes, which were; 704, 724, 1341, 1377, 1412, 1457 and 1516.
- 1964 L'Udovit Vittek from Bratislava, Czech Republic also published a CPSS of order 25 with size 235. This is the same order 25 size 235 published by Federico. Priority is given to Federico due to earlier publication.
- In 1964 P. J. Federico published a CPSS with side 429 of order 26 using a type of Fibonacci sequence construction published by S. Basin in 1963.
- 1965-69 E. Lainez, a Spanish engineer, constructed 2 CPSSs with sides 360, 460 of orders 26 and 27 respectively.
- 1972 N.D. Kazarinoff and R. Weitzenkamp proved the non-existence of a CPSS of order less than 22.
- 1979 Paul Leeuw publishes his thesis on Compound Perfect Squared Squares. He finds there are no CPSSs below order 24. and there is one and only one (THW 24:175) CPSS of order 24. He also produced a total of 2211 CPSSs in orders from 24 to 33. However only a handful of these were published.
- 1982 A. J. W. Duijvestijn, P. J. Federico, P. Leeuw published a paper expanding Leeuw's thesis with the same results as the thesis; they established the lower limit of the order of CPSSs and searched to find all that can exist up to and including order 24. The main results were; There are no CPSSs below order 24. and there is one and only one (THW 24:175) CPSS of order 24. Of the 2211 CPSSs produced 1942 were new discoveries. The particular discoveries were not individually published, it is not always possible to infer which particular CPSS were discovered and which werent as we dont have a complete record of prior discoveries, so many have been 'rediscovered' since. However by analysing the results from 1982 and comparing them to 2010 results, it is possible to infer the particular CPSS discoveries made by Duijvestijn, Leeuw and Federico in orders 26, 27 and 28.
- 1980 -1999 Willcocks, Federico, Muller, Skinner, Morley and Bouwkamp continue to discover new CPSS transforms and steadily add more CPSS discoveries to Orders 28, 29 and above.
- 1999 I. Gambini published his doctoral thesis 'Quant aux carrés carrelés' on squared squares. He found the known CPSSs (and SPSS) up to and including order 26. He also published a table of CPSR ( and SPSR) counts up to and including order 24. For order 26 he identified 100 CPSS isomers which is correct, 92 isomers were known before Gambini, the additional square which completes the order (with side 512) has 8 isomers and was probably found by Paul Leeuw in 1979. However Gambini did not mention this CPSS in his thesis. This CPSS was evidently 'rediscovered' in 2010 by Anderson and Pegg.
- 2010 S.E. Anderson and Ed Pegg Jr. enumerate all CPSSs up to order 28. Richard K. Guy, Ed Pegg Jr and Stuart Anderson collaborated to extend the known solutions to the Mrs Perkin’s quilt problem. Mrs Perkin’s quilts include all combinations of simple, compound, perfect and imperfect squared squares. Using Brendan McKay and Gunnar Brinkmann’s planar graph generation software plantri and electrical network tiling software written with C++ standard libraries and Boost Ublas library (by Anderson), Anderson and Pegg enumerated all perfect squared squares and simple imperfect squared squares (SISSs) to order 28. As a subset of the quilt enumeration Anderson and Pegg produced all CPSSs up to and including order 28. In January 2012 some errors were found in records of order 28 compounds isomers. A recount established a bijection between isomers and the graphs extracted in earlier processing, the original counts (Order 28; 143 CPSS , 948 isomers were confirmed). In isomer classes of CPSS, orders 24 to 28, the final counts are;
- 1 CPSS of order 24, with 4 isomers, (24:175 THW)
- 2 CPSSs of order 25, with 12 isomers, (25:235 PJF (4) & 25:344 PJF (8))
- 16 CPSSs of order 26, with 100 isomers, including 1 CPSS, with 8 isomers, with side 512 not previously identified, (discovered in 1979, but not published by Leeuw and rediscovered but not identified by Ian Gambini in 1999) which completed this order.
- 46 CPSSs of order 27, with 220 isomers, including 4 CPSSs not previously known (with sides 345a, 624a, 648a, 857a), and 3 CPSSs which had been discovered by Leeuw in 1979, but never published, (27:804a, 27:820a and 27:824a) which completed this order.
- 143 CPSSs of order 28, with 948 isomers, including 50 CPSSs not previously known, which completes this order. Paul Leeuw found 23 new CPSSs in this order in 1979 but only 1 was published. Out of the remaining 22, Anderson and Pegg rediscovered 14 CPSSs in the scope of Leeuw's program (28:753a, 28:811a, 28:1032a, 28:1049a, 28:1069a, 28:1075a, 28:1078a, 28:1093a, 28:1131a, 28:1164b, 28:1170a, 28:1170b, 28:1208a and 28:1229a). These discoveries have been attributed to DFL (Duijvestijn, Federico and Leeuw) 1979.
- 2011 S.E. Anderson and Stephen Johnson commenced order 29 CPSSs, and processed all 2-connected min degree 3 graphs with up to 15 vertices. This leaves the largest graph class, the 16 vertex class, still to be processed.
- 2011 October, Stephen Johnson discovers 60 CPSSs from order 30 to order 36.
- 2012 January, Geoffrey Morley discovers over 100 new CPSSs in orders 31, 32, 33 and 34.
- 2012 March, Geoffrey Morley discovers hundreds more new CPSSs in orders 29, 31, 32, 33 and 34. This makes a total of 578 new CPSSs discovered by him in 2012 so far.
- 2012 April, Stuart Anderson produces millions of CPSSs in orders 41 to 60 by substituting PSSs into PSSs. Out of the millions of CPSSs produced, only those with small sides are shown on this site, (depending on the quantity produced in each order). Order 40 is the first order where this can be done, due to recent discoveries by Jim Williams. Order 41 is the second order where this can be done (Duijvestijn's order 21 :112 inserted into its elements and scaled). This method can produce unlimited CPSSs as it can be applied iteratively. By substituting the existing catalog of PSSs from this website into itself just once, well over 10 billion CPSSs can be produced. If the operation was repeated twice, approximately 10^22 CPSSs could be produced, this is about the number of grains of sand on the Earth.
- 2012 July, Stuart Anderson produces over 100,000 CPSSs in orders 34 to 44 by combining same size pairs of SPSRs of orders 16 - 21 with no element in common (disjoint n-tuple SPSRs). If there are more than several thousand in an order, only the smaller CPSS of that order are shown on this website.
- 2012 October, Geoffrey Morley discovers 23 (161 isomers) new rotor-stator CPSSs, in orders 39 [1 new], 45 [2 new], 51 [13 new] 53 [3 new] and 57 [2 new] including 39:3781a (7) (isomers) GHM 2012. Only two other rotor-stator CPSSs of order 39 are known! (39:1813a(7) TTF 1940 and 39:4639a(7) RLB 1950.)
- 2012 October/November, Stuart Anderson processes the remaining 16 vertex, 2-connected, minimum degree 3, 30 edge graphs of order 29, using the Amazon Elastic Cloud supercomputer and new software which he wrote. Combined with the earlier 13, 14 and 15 vertex, 30 edge 2-connected graphs processed by Pegg, Johnson and Anderson, this completes the enumeration of order 29 CPSSs.
A total of 412 CPSSs of order 29 and 2308 isomers were found. Leeuw discovered 101 of these order 29 CPSSs in his 1979 thesis but we do not know which ones.
- 2013 January, Jim Williams of Massachusetts, USA writes his own program and finds both SPSSs and CPSSs. He found 31979 CPSSs. They include ;
- 2 order 24 CPSS isomers (already known)
- 4 order 25 CPSS isomers (already known)
- 18 order 26 CPSS isomers (already known)
- 61 order 27 CPSS isomers (already known)
- 185 order 28 CPSS isomers (already known)
- 469 order 29 CPSS isomers (already known)
- 1064 order 30 CPSS isomers (many new discoveries)
- 2959 order 31 CPSS isomers (many new discoveries)
- 7605 order 32 CPSS isomers (many new discoveries)
- 19612 order 33 CPSS isomers (many new discoveries)
- 2013 March, June; Stuart Anderson publishes (March) to the Arxiv and updates (June) a paper on 'Compound Perfect Squared Squares of the Order Twenties'.
- 2013 May, Lorenz Milla and Stuart Anderson enumerate CPSSs of order 30. Lorenz processes 13, 14, and 15 vertex, 2-connected, minimum degree 3, 31 edge graphs of order 30 (8,377,405,224 graphs), then Stuart and Lorenz process half each of the 16 vertex, 2-connected, minimum degree 3, 31 edge graphs (35,873,044,824 graphs) to find 941 CPSSs, with 5668 CPSS isomers in order 30. Stuart and Lorenz both wrote new software; Stuart implemented a technique of Tutte's, used by Duijvestijn in his thesis, that factors the Kirchhoff matrix determinant of a graph into a product of 3 numbers as follows; 2, a square free number and a square number (this is a necessary condition for a graph to produce a squared square). This method resulted in a 3x speed up of the search. This part of the search was implemented as a program called sqfree, available on the downloads page. Lorenz also produced new software to produce the all isomers of the most common types of CPSSs and identify the canonical tablecode representative from the isomers of a CPSS.
- 2013 June, July and August ; Lorenz replaced the Boost library with C arrays and handwritten linear algebra routines; LU decomposition was replaced with LDL decomposition (planar maps are symmetrical, so LDL Cholesky decomposition is possible and twice as fast as LU decomposition). Lorenz also wrote a plantri plugin to filter graphs using the determinant factorisation technique as they were produced, he was also able to speed up the routines in Stuart's sqfind and sqt programs and combine the plantri plugin and sqfind into a single program mandrill (a combination of the names Milla and Anderson). The end result was squared square software 35 times faster than what was used several months ago. This made it possible to complete the enumeration of order 31 and 32 compound perfect (CPSSs), simple perfect (SPSSs) and simple imperfect squared squares (SISSs) in under 2 months. The computations were done by Lorenz on his computers. There are 17351 order 31 CPSS isomers and 2788 order 31 CPSS isomer classes, 52196 order 32 CPSS isomers and 7941 order 32 CPSS isomer classes. A second run, conducted in September 2013 by Anderson and Milla confirmed these counts, and identifed 2 CISSs in orders 31 and 32 which had been previously incorrectly included as CPSSs on the website. These two CISS were consequently removed from the website CPSS listings.
- 2013 September and October ; Lorenz Milla and Stuart Anderson redid the computations for order 31 and 32 CPSSs, as a bug in the determinant factorisation was identified which affected a small number of cases. No changes to order 31 and 32 CPSSs were required as a result of the second run. The largest graph classes in these computations were those with 17 vertices and 33 edges, Lorenz extended the computations to graphs classes with 17 vertices and where the numbers of edges runs from 34 to 40. This resulted in a number of new CPSS discoveries in orders 33 to 39.
- 2013 December ; Stephen Johnson collated the results of his squared square searches in early 2013 and made them available. A number of new CPSS discoveries in orders 33-36 were found, these have been included in the website.
- 2014 March ; Brian Trial uses a new 'Ell-Munch' method to find PSSs where there are large gaps in the current catalogues. He found 114795 PSSs, 83 of them CPSSs in orders from 44 to 86. By “ell,” we mean any six-sided figure whose sides are parallel to the coordinate axes (Henle 2008).
- 2014 April. Jim Williams enumerated all CPSSs (and isomers) up to order 36. Jim wrote new software to implement a substitution method, similar to Duijvestijn, Federico and Leeuw (1982), but with significant modifications to speed up the search. A outline of the method, by Jim;"The idea was to enumerate “almost perfect squares” or APSs which consist of a square subdivided into a number of smaller squares, each of different size, plus [at least] one rectangle. Then cross check this with a list of perfect rectangles to find combinations that create a perfect square. I think using this technique it should be easy to enumerate all compound perfect squares up to order 36, and with some significant compute effort probably up to somewhere in the 38-40 range."
- 2018 August ; Jim Williams enumerated all CPSSs (and isomers) up to and including order 39.
Initials of person attributed CPSS discovery & totals Order_33 Order_34 Order_35 Order_36 Order_37 Order_38 Order_39 SEA 1 0 0 225 0 1207 0 S_J 12 16 7 3 0 0 0 C_M 1 1 1 1 1 1 1 CJB 9 18 0 2 2 4 1 PJF 44 11 13 0 4 2 11 THW 7 1 0 0 1 0 0 GHM 296 141 0 2 3 0 1 M&A 641 415 97 37 2 0 0 L_M 0 0 0 0 1 1 0 RLB 0 0 0 0 0 0 1 TTF 0 0 0 0 0 0 1 JBW 2013 7016 4 13 27 53 102 182 Total in 2013 8027 607 131 297 67 1317 198 JBW 2014 14386 61666 172199 466211 0 0 0 JBW 2018 0 0 0 0 1239675 3256061 8430730 Complete CPSS class total
(right click & save link as a zipped postscript file for a booklet of the CPSSs)
22413 (1Mb) 62273 (4Mb) 172330 (11Mb) 466508 (30Mb) 1239742 (78Mb) 3257378 (210Mb) 8430928 (564Mb) Complete CPSS isomer total
150669 429458 1206181 3337989 8961794 23989218 62894424
CPSSs counts for orders 24 to 39 are now complete (subject to confirmation *).
* Proof of completeness for CPSS orders 33 to 39 is subject to proof of some conjectures used in the enumeration process. The results for orders 24 to 32 are identical to the previous results for these orders.
CPSSs counts by order are listed in the OEIS as sequences;
- A181340, Number of compound perfect squared squares of order n up to symmetries of the square and its squared subrectangles. (This counts only one representative of each isomer class)
- A217155, Number of compound perfect squared squares of order n up to symmetries of the square. (These are the isomer counts) .
Credit for Discovery
The people listed below have published or have been credited with the discovery of compound squared squares.
- AHS - Arthur H. Stone (1916-2000);
- AJD - A.J.W. (Arie) Duijvestijn (1927-1998);
- A&J - Stuart E. Anderson (1959-) & Stephen Johnson (1958-);
- A&M - Stuart E. Anderson & Lorenz Milla ;
- A&P - Stuart E. Anderson & Ed Pegg Jr (1963-);
- B_T - Brian Trial (1966-);
- C_M - Carsten Müller ;
- CJB - Christoffel J. (Chris) Bouwkamp (1916-2003);
- DFL - Duijvestijn, Federico and Leeuw;
- E_L - Enriquee Lainez ;
- F&S - P.J. Federico & R.P. Sprague (PJF constructed 23 CPSSs of order 54 based on RPS's order 55 CPSS);
- GHM - Geoffrey H. Morley (1944-);
- I_G - Ian Gambini ;
- JBW - Jim B. Williams ;
- JDS - Jasper D. Skinner II (1947-);
- L_M - Lorenz Milla ;
- M&A - Lorenz Milla & Stuart E. Anderson ;
- PJF - Pasquale J. Federico (1902-1982);
- P_L - Paul Leeuw ;
- RLB - R. Leonard Brooks (1916-1993);
- RPS - Roland P. Sprague (1894-1967);
- SEA - Stuart E. Anderson ;
- S_J - Stephen Johnson ;
- THW - T.H. (Theo) Willcocks (1912-2004);
- TTF - The Trinity Four (R.L. Brooks, C.A.B. Smith, A.H. Stone, W.T. Tutte);
- WTT - William T. (Bill) Tutte (1917-2002).
- UNK - Unknown.
Generating CPSSs from Electrical Network Graphs
Using Brendan McKay and Gunnar Brinkmann's plantri software, graph classes specified as 2-connected (exactly 2-connected, not at least 2-connected), minimum degree 3 (also known as homeomorphically irreducible - no vertex of degree 2 is permitted), simple planar maps in the sphere of up to 30 edges (graphs (v,f,e) where v ≤ f) have been enumerated and generated from the commandline ; UseThe 2-connected graphs and their dual graph classes, have different counts, but the duals dont need to be generated or processed for CPSSs.
- plantri -pc2m3xv n filename, to count and generate graphs by node and save to file
- plantri -pc2m3e#xv n filename to count and generate graphs by node and edge and save to file
- plantri -pc2m3e$:#xv n filename to count and generate graphs by node and edge range and save to file, where $ is lower edge bound, # upper edge bound
- to count graphs only (not generate them) add the u switch to the commandlines above, and the filename is no longer necessary
Graph classes (v,f,e) and (f,v,e), where v + f = e + 2, are dual graph classes. The dual graph can be generated from the primary graph, and it produces the same tiling, so dual graphs dont need to be generated and processed, but there is a complication. With 2-connected maps, unlike 3-connected maps, the numbers of graph and dual classes produced by plantri are not identical. Graph class (v,f,e) where f > v, has lesser numbers than the dual graph class (f,v,e).
What is the nature of these extra graphs? The reason they are produced is, plantri produces simple graphs and the 2-connected duals are sometimes multi-edge non-simple (the multi-edges are not adjacent in the edge adjacency cyclic order around a given vertex) and as multi-edge graphs, they get excluded from the count and output for simple graphs. These graphs are also excluded from perfect compound square tiling processing as multi-edge graphs always produce imperfect tilings (multi-edges have the same currents in the electrical resistor graph and produce square tiling elements the same size). The exception to this rule is if one of the multi-edges (or equivalently, one of its dual edges) is the battery edge, then a perfect tiling can result. This is the case for compound squared rectangles, but not compound squared squares. In its simplest form, the perfect compound squared rectangles produced from these graphs have a square with its height equal to the squared rectangle height, these are called 'trivial' CPSRs. In higher orders the full height square can also be 'sandwiched' between two or more squared rectangles.
In summary, for square tilings of all kinds, the number of graphs to process is always less than the total for a complete edge class, as a graph class (v,f,e) and its dual class (f,v,e) produce the same tilings. The only difference being the tiles are rotated 90 degrees, and the dual class may include additional tilings from multi-edge duals in the case of 2-connected graphs.
The classes in the table below, outlined in black are self-dual, they are the largest vertex-edge class of each tiling order and need to be processed for compound tilings.
The requirement for minimum degree 3 graphs is needed to filter out graphs that always produce imperfect solutions, because degree 2 vertices in an electrical resistor (all resistors 1 Ohm) network-graph produce the same current on entry and exit to the vertex, creating 2 adjacent imperfect squares the same size in the tiling. Note that the minimum 2-connected simple, minimum degree 3 planar maps share the same graph classes (v,f,e) as the 3-connected planar maps with the exception of the triangulations, which are exclusively 3-connected graph classes.These exactly 2-connected, minimum degree 3, simple planar map classes (v,f,e)> were processed to produce Compound Perfect Squared Squares (CPSSs) up to Order 32.
This method, developed by Stuart Anderson, and recently extended by Lorenz Milla was used successfully used to produce all perfect compound squared squares (CPSSs) from order 24 to 32. A similar method for enumerating compounds (CPSSs and CPSRs) was developed by Ian Gambini in his thesis in 1999 to produce perfect squares to order 26. One produces all the simple planar map classes (v,f,e) where v ≤ f of 2-connected minimum degree 3 planar graph embeddings for a given number of edges, these graphs can then be treated as electrical resistor networks. Solving the Kirchhoff equations for the network, produces node voltages and edge currents, which give the dissections of squared rectangles and squared squares. This process, like Duijvestijn's method for simple perfect squared squares, and like Gambini's graph methods, finds all compound perfect squares of a given order. The graphs can be generated and output by plantri. Plantri produces all the multiple planar embeddings of a 2-connected graph, in the case of the graph of a compound perfect square, these graph embeddings correspond to the isomers of the compound square.
The squared squares are encoded using Bouwkampcode or tablecode.
Updated on ... September 17th, 2018