Skip to content
Little GolemMake your next move.

Search for small alternating planar graphs

Public forum discussion.

General

#101 · wccanard

12 Feb 2008

"Yes, he needs to start some games": this was put in a year or so ago by Richard, to stop spam. The idea was that it was probably harder to write code for spambots if they also had to be able to play a passable game of hex :-)

The infinite graph: perhaps a way of making your question meaningful is to ask for a locally finite tiling of R^2 [so every point in R^2 has to be either a vertex, or on a piecewise smooth edge with finite length, or in a polygon with finite area and piecewise smooth edges blah blah blah] and which has the right local properties. Then you don't have to worry about infinite regions or "dot dot dots" in the middle of graphs. My guess is that this is what you implicitly mean. So, for example, my infinite glueing of pentagons above wouldn't count above because it can't immediately be tweaked to cover all of R^2.

It wouldn't surprise me if one could take one of the examples above, arrange it so it has a square as a boundary, and then tile the plane with squares in the obvious way and put a copy of the graph into the square in a sufficiently clever way (the issue is the orientation) that gives an example of an infinite graph with a global bound (16 or so) on the degrees of the vertices. But I didn't try this yet, and it might not work. A good exercise :-) It won't give a 3,4,5 tiling though.

#102 · Tasmanian Devil

12 Feb 2008

I don't find an "R^2-covering non-(3,4,5)"-graph all that appealing; I like that the (3,4,5)-restriction forces it to be R^2-covering. ;-)

#103 · Tasmanian Devil

12 Feb 2008

Btw, I am having some serious problems with my PC at home (currently I have hooked up my old laptop in order to get online), so the ggb-files for the drawings may be lost.

#105 · Carroll

13 Feb 2008

Take Tas example

<br/>Numbering the outer sides of the square boundary with the number of sides of the corresponding face, is not :<br/><br/> --5---4--<br/> 3   3   3<br/> --4---5--<br/> 3   3   3<br/> --5---4--<br/><br/>a desired tiling (each of the four squares is Tas figure straight or mirror)?

29 vertices

#106 · Carroll

13 Feb 2008

I try again, you need two numbers to show a triangle is not touching another one and so on :

<br/> --5----3--<br/> 3   35   4<br/> --4----3--<br/> --3----4--<br/> 4   53   3<br/> --3----5--<br/>

#108 · wccanard

13 Feb 2008

@Carroll: what are you trying to do? Tile R^2? Did you check there are no corners of squares which are adjacent and have the same degree? I think you have to explicitly say which way round you are putting the square: the two outside triangles have outer vertices of different degrees. Am I making any sense? When you glue the squares together the oudside vertices suddenly get big random degrees and you have to make sure there is no problems there.

#109 · Tasmanian Devil

14 Feb 2008

When trying to tile R^2 with equal tiles, I've thought of a possible approach but not gotten very far yet. The average corner angles of triangles, quadrangles and pentagons are 60, 90 and 108 degrees respectively. The sum of the angles around a given vertex in the plane must be 360 degrees. The angles will in general not actually be 60, 90 or 108, but by replacing all angles in any face by their average, the average over the vertices will be the same.

In other words, a tile must consist of vertices such that the sum of (180 - 360 / (n-2)) over the number of sides of the faces is 360 on average.

There are r vertices of degree 3 and r - 4 of degree 5, of which all but 4 belong to one triangle, two quadrangles and two pentagons. The averaged angle sum for the vertices of degree 3 is 60 + 90 + 108 = 258 degrees, and for almost all vertices of degree 5 it is 258 + 90 + 108 = 456 degrees. So their average is 357 degrees.

Now let's look at the averaged angle sum for the possible types of vertices of degree 4.

Faces / Averaged angle sum

(3,3,4,4) / 300

(3,3,4,5) / 318

(3,3,5,5) / 336

(3,4,4,5) / 348

(3,4,5,5) / 366

(4,4,5,5) / 396

Based on this one could work out possible combinations that could be the vertices of a tile. And one would have to keep in mind that the number of vertices of degree 4 should be between 1 and 1.5 times the number of vertices of degree 3.

I don't have time to work more on this for a few hours now.

#110 · Carroll

14 Feb 2008

@wccanard: yes that is what I want to do,

let use only Tas 29 figure with rotations (no mirror), one copy can be represented like this :

<br/> -------<br/> |4 3 5|<br/> |5   5|<br/> |5 3 3|<br/> -------<br/>

where central number is number of edges of external faces and corner number is degree of corner vertices.

Having four copies glued together we get different degrees for adjacent vertices (sum of degrees minus 4) :

<br/>3 4   5 5   3 4<br/> -------------<br/>3|4 3 5|5 5 3|4<br/> |5   5|3   3|<br/>5|5 3 3|4 5 5|<br/> -------------<br/>5|5 5 3|4 3 5|<br/> |3   3|5   5|<br/>3|4 5 5|5 3 3|4<br/> -------------<br/>3 4   5 5   3 4<br/>

let me know if I still missed something

#111 · Tasmanian Devil

14 Feb 2008

I am afraid I haven't studied Carroll's idea but I would like to ask:

Is it possible to tile the plane with triangles, quadrangles and pentagons subject to the following restrictions?

The vertices of each triangle have degrees 3, 4 and 5

The vertices of each quadrangle have degrees 3, 5, 4 and 5 in that order

The vertices of each pentagon have degrees 3, 4, 5, 4 and 5 in that order (clockwise or counter-clockwise)

The faces of each vertex of degree 3 have 3, 4 and 5 sides

The faces of each vertex of degree 4 have degree 3, 5, 4 and 5 in that order

The faces of each vertex of degree 5 have degree 3, 4, 5, 4 and 5 in that order (clockwise or counter-clockwise)

#112 · wccanard

14 Feb 2008

@Carroll: Looks good to me!

@Tas: Carroll has tiled the plane with faces of degrees 3, 4, and 5, but a positive proportion of his vertices have degree 20.

@Tas again: why are you putting these extra constraints on the pentagons etc?

For example in your earlier post you said that "almost all" vertices of degree 5 meet only one triangle. I don't really know what you mean. In any chain of triangles the degrees of the vertices joining the chain together are 4,5,4,5,4,...

Last thing: did you work out the average angle sum at a vertex in the configuratio you suggest in the post just above? If it's not 360 then probably you're already dead. Or did you rig it so that it was 360?

#113 · wccanard

14 Feb 2008

One last thing: I think that probably the time has come to break the news to this thread that a polygon with 4 sides is called a "quadrilateral" (in British English, at least...). My old school had a quadrangle, which did have 4 sides, but I think that the typical quadrangle is big enough to park a car in.

#114 · Tasmanian Devil

14 Feb 2008

The average of the sums for the vertices of degree 4 must lie in [364, 366], and the simplest thing would then be to have all of the type (3,4,5,5) for which the sum is 366. With equally many vertices of degree 3, of degree 4 and of degree 5 of the types described above, the average for all is 360. So I am wondering if we can do a tiling with only these elements. Otherwise things seem to get pretty complicated.

It is part of the proof that there are r-8 vertices of degree 5 that only meet one triangle and only 4 others that meet two triangles. If this contradicts arbitrary amounts of chains of triangles, well, then there can't be too many chains of triangles.

#115 · Carroll

14 Feb 2008

@wccanard: degrees of vertices are 3,4,5,10 and 16, I'll try to post a drawing.

Would you say it is an infinite alternating planar graph? Or does the problem lie on the external missing face? What if we tile a sphere or a torus?

#116 · Tasmanian Devil

14 Feb 2008

It seems that you have constructed an infinite alternating planar graph, but the focus is currently on (3,4,5)-alternating graphs. ;-) It's not planar if you tile a torus.

#117 · Ingo Althofer

14 Feb 2008

I am sorry to tell you that I have to leave this

interesting thread (now centering around alternating

tilings of the plane) for some time.

Semester is over (tomorrow are the last classes),

and a non-planar island is waiting, where I will

stay "isolated" for three weeks, only with my

wife and the volcano. No internet, no email.

I hope to be back in the wired world around March 10.

Keep busy, Ingo.

#119 · Carroll

14 Feb 2008

Yes thanks for these interesting ideas, have a good time!

@Tas: how do you duplicate objects (many polygons at a time) in Geogebra?

#121 · ypercube

15 Feb 2008

Enjoy your vacation in the torus island, Ingo :)

(got you, FatPhil and Gregorio ;)

#123 · Tasmanian Devil

17 Feb 2008

OK I found an infinite (3,4,5)-alternating graph. It's so simple it's almost boring. ;-)

#124 · FatPhil

17 Feb 2008

Nope, too interesting, it's askew and contains irregular shapes. This is the correct boring rendering of its tile:

<br/>    +-------+<br/>   /         \<br/>  /           \<br/> /             \<br/>+-------+-------+<br/> \     /       /<br/>  \   /       /<br/>   \ /       /<br/>    +-------+<br/>

#126 · wccanard

17 Feb 2008

We know there are the same number of triangles and pentagons in any tiling, and have upper and lower bounds for the number of quadrilaterals, but the lower bound is attained here, right? Can one get the upper bound? e.g. find a tile with 3 quadrilaterals, 2 triangles and 2 pentagons? Given the simplicity of the tile above this doesn't seem out of the question.

#127 · wccanard

17 Feb 2008

PS if Ingo is trying to make a game based on this, then the above infinite tiling might make a fine board :-)

#128 · Tasmanian Devil

17 Feb 2008

Yes, the lower bound is attained here. But again, if we try to change anything, we have to take the average angles and things into consideration, and things get complicated very quickly.

In order to find the last tiling, I not only restricted myself to the 3-5-4-5 quadrilaterals, but I also put restrictions on the orientations of triangles and pentagons as well as vertices of degree 3 and 5. Turned out that if the orientation of each one was to be fixed, there was essentially only one possibility, namely the one I have shown.

The "most interesting open problem" on alternating graphs seems to keep changing; I guess now it's how close to 3/2 we can make (v4+5)/r for (3,4,5)-alternating graphs? :-)

#129 · Tasmanian Devil

17 Feb 2008

If a tile attains the upper bound, the averaged angle sum of the quadrilaterals must be 364. It is in fact possible to achieve this with only three quadrilaterals: (3, 4, 5, 4), (3, 4, 5, 4) and (4, 5, 4, 5).

#131 · wccanard

17 Feb 2008

I think I have a tile with the required properties. 2 triangles, 3 quadrilaterals (with 3454,3454,4545) and two pentagons.

The bad news is that I have it drawn on a piece of paper and have got a lot of housework to do, so I'm not going to spend 20 minutes making a PDF :-)

OK so let me describe it and someone else can draw it. Sorry. The basic idea is the standard tessellation of the plane with regular octagons and squares. The trick is that I'll make the octagon with two of the basic hexagon tiles above (deformed appropriately, of course, so the octagon is regular but the hexagons aren't). That gives me 2 triangles, 3 quadrilaterals and two pentagons, but one quadrilateral is "different" to the other two (the one not in the octagon) and that's the 4545 one.

OK so here's a bit more detail. Take a regular octagon. Label the vertices ABCDEFGH, with A at about 1 o'clock, B at 2 o'clock, C at 4 o'clock and so on, up to H at 11 o'clock. Now draw CH, HD and DG and let the midpoints be X,Y,Z; now draw the line XYZ. If I got it right, and you got it right, that has chopped up the octagon into 2 pentagons, 2 quadrilaterals and 2 triangles.

Now put a square on top; that's the tile!

WARNING: we need to flip some of them over before they tessellate correctly. Take the octagon and square that we've made, and now pile infinitely many on top of each other. That's a strip.

Now flip that strip in a mirror with the axis of symmetry being up-down.

That's the second strip. Fit 'em together. Now flip again (back to the

original state) for the 3rd strip. If the squares not in the octagons

have got vertices of degrees 4,5,4,5 then you're doing it right.

That's it! Sorry again for the verbal description...

wcc

#132 · FatPhil

17 Feb 2008

<br/>       +-----+<br/>       |     |<br/>       |     |<br/>       |     |<br/>      H+-----+A<br/>      /|\     \<br/>     / \ \     \<br/>    /   | \     \<br/>   /    |  \     \<br/>  /     \   \X    \<br/>G+       |   +     +B<br/> |\      |  / \    |<br/> | \     \ /   \   |<br/> |  \     +Y    \  |<br/> |   \   / \     \ |<br/> |    \ /  |      \|<br/>F+     +Z  |       +C<br/>  \     \   \     /<br/>   \     \  |    /<br/>    \     \ |   /<br/>     \     \ \ /<br/>      \     \|/<br/>      E+-----+D<br/>

#134 · wccanard

18 Feb 2008

Thanks guys :-) You've certainly drawn what I was thinking, so if it's not a correct 3,4,5 tiling then the error is mine not yours.

Both the hexagon and the octagon+square give infinite tilings of the plane but I suspect that you can regard them as finite tilings too. The octagon+square can be regarded as a finite tiling of a torus, which means that TD's fundamental formulae will not quite apply; V-E+F will be 0. I don't know if that changes TD's expectations for a tiling; the plane gives an unramified cover of the torus and one way of doing the maths for a 3,4,5-tiling of the plane would be to consider it as a finite tiling of the torus. Presumably the hexagon tiling also lifts to a finite tiling of the torus too (dim memories of what you get by identifying opposite edges of a hexagon); it's just harder for me to visualise :-)

#135 · Tasmanian Devil

18 Feb 2008

Yes, any tiling that is periodic in two directions can be used for a finite tiling of a torus (just stretch it a bit if necessary) but I am skeptical about torus tilings when we want planar graphs. The Heawood graph is the graph of a tiling of a torus with seven hexagons, but it is not planar.

I just discovered another interesting property your graph possesses: Its dual is of the second type I "predicted", with quadrilaterals of the types 3434, 4545 and 4545!

#136 · wccanard

18 Feb 2008

I understand that a finite graph on a torus might not be a planar graph---I'm not saying that. I'm saying that a finite graph on a torus gives an infinite planar graph simply by pulling back the graph from the torus to its universal covering space, which is the plane. The reason I mentioned it was that it enables one to apply "finite" "3,4,5-techniques" rigorously to the infinite planar graphs above.

The problem one would have with the naive approach, i.e. drawing a huge circle within an infinite graph and analysing the finite graph that lies entirely within the circle, is that the outer face will have a huge number of faces, so some of your lemmas above (analysing finite 3,4,5-graphs) don't apply, whereas they will all apply to the finite torus graph when the Euler formula is modified appropriately.

#140 · Tasmanian Devil

22 Feb 2008

Back to the finite (3,4,5)-alternating graphs:

We have seen that there are always exactly four pentagons with two vertices of degree 3. Each of them must either have exactly one vertex of degree 4 or have exactly one vertex of degree 5.

But how many are there of each type among the four?

If I counted correctly, each possible combination is represented among the ones that Frank found with at most 26 vertices. So there are no further restrictions.

Just a minor observation.

#141 · Tasmanian Devil

28 Feb 2008

With FatPhil's representation of the first infinite (3,4,5)-alternating graph above, we see that it is a subgraph of the triangular grid. I wondered if we could classify all (3,4,5)-alternating graphs that are subgraphs of the triangular grid, as this seems pretty restrictive. While I am nowhere near a complete classification, I did stumble across a new one while experimenting. The tile looks like this:

It gives rise to the following graph:

#142 · wccanard

28 Feb 2008

Does mine fits into a triangular grid?

#143 · Tasmanian Devil

28 Feb 2008

It seems that it is only possible if we allow some edges to have length 2 units.

#144 · Tasmanian Devil

29 Feb 2008

Unfortunately (in my opinion), there are infintely many different (3,4,5)-alternating graphs that are subgraphs of the triangular grid. Here is a way to construct infinitely many different ones.

Each tile is supposed to continue in the same pattern indefinitely to the right and to the left. So we can imagine coming from above in the plane and adding tiles downwards.

We can get infinitely many different ones simply by adding tiles of the type

(A)

and

(B)

in any order. My first graph from earlier in the thread is a special case (with all tiles equal).

If we want to create a graph containing vertices that do not belong to any triangles (a property that neither of my first two graphs has) we can stop at any point and add a tile of the type

(C)

provided all the subsequent tiles are of the type

(D)

Note that these graphs have the property that any two vertices that are neighbours in the grid have different degrees, a property not shared by the graph I gave yesterday.

#145 · Ingo Althofer

10 Mar 2008

Hello,

holidays are finished now. In my mailbox

I found very interesting stuff by Dr. Karl

Scherer. He has written a program for "Zillions

of Games" called "Graph Puzzles". In this program

he presents the (17,17)-Schneider Graph (in a new nice

drawing) as well as several other alternating planar

graphs which he found for different numbers of

vertices/faces.

As Karl was not aware of this thread some of his graphs

are isomorphic to ones in this thread. Unfortunately

Karl cannot post here, as he is not an active player

on Little Golem :-(

A picture of his drawing of the (17,17)-Schneider graph

may be found on my website, at

http://www.althofer.de/alternating-planar-graphs.html

Greetings, Ingo.

#146 · Tasmanian Devil

2 Mar 2009

OK I don't know how to say this without sounding conceited, but may I suggest that anyone who is interested in the images I have posted in this thread download them in the near future. My old free web page provider is closing its services in a couple of months and all the contents will be deleted. (My new home page is www.neutreeko.net.)

#147 · Ingo Althofer

9 Feb 2013

The hot time of "alternating planar graphs" here in LittleGolem's
forum was almost five years ago. Now there is new progress:

Gunnar Brinkmann (U Gent) has shown with massive computer help
that there is no alternating planar graph with less than 17 vertices;
and there exist exactly two non-isomorphic such graphs (both with 17
vertices and 17 faces).

New drawings of Schneider-17 and Brinkmann-17 can be seen
here.

Ingo.

#150 · Ingo Althofer

11 Feb 2013

Hi Phil,

you mean the 3d-printed body, right?
It is somewhat heavier than water.
It is stable (no problem to throw it from one meter height on solid ground).
It is thermally stable until 120 degree Celsius.

The process of printing took almost three hours.
The cartridges for the 3-d-printer are rather expensive.
The price for the material in the Schneider-17 is
between 100 and 150 Euro.

I have added a new picture making clear the size of the 3d-print.
Click at the link in my answer above. (Also, now all text on the site
is in English.)

Ingo.
Cheers, Ingo.

Last page