Plotting graphs with nice automorphism groups

[Nathann Cohen]

Hellooooooooo everybody !!!

Being lost in a foreign country, my hobbies get weirder and weirder. These days I find myself playing with graph drawings because of a colleague of mine, Thomas Connor.

We are currently trying to plot his graphs in some meaningful way, and his graphs are veeeerry symmetrical. Hence we would like to find a way to plot them using the information contained in their automorphism group, using some properties we think of along the way. Hence, this email : would anyone here happen to have examples of nice symmetrical graphs which have nice representations ? What we actually need right now (besides good ideas for a plotting heuristic) is a collection of some graph to test it on. If you have some you like, could you please tell me how to build them through Sage ? If we finally get anywhere we will send you back nice pictures to get your advice on the drawings produced !

I initially asked Jason who thought some of you may be interested in the adventure :-D

Thaaaaaaaaaaaaaaaaaaaaaaaaaaank you for your thoughts ! ;-)

Nathann

P.S. : Oh, and if you already know of some code producing such drawings, please share it !

[David Joyner]

On Sat, May 5, 2012 at 5:51 AM, Nathann Cohen <nathan...@gmail.com> wrote:
> Hellooooooooo everybody !!!
>
> Being lost in a foreign country, my hobbies get weirder and weirder. These
> days I find myself playing with graph drawings because of a colleague of
> mine, Thomas Connor.
>
> We are currently trying to plot his graphs in some meaningful way, and his
> graphs are veeeerry symmetrical. Hence we would like to find a way to plot
> them using the information contained in their automorphism group, using some
> properties we think of along the way. Hence, this email : would anyone here
> happen to have examples of nice symmetrical graphs which have nice
> representations ? What we actually need right now (besides good ideas for a
> plotting heuristic) is a collection of some graph to test it on. If you have
> some you like, could you please tell me how to build them through Sage ? If
> we finally get anywhere we will send you back nice pictures to get your
> advice on the drawings produced !

I added a bunch to http://trac.sagemath.org/sage_trac/ticket/9136
a few months ago. They are all nice and if I remember have nice aut gps.
Hope they help:-)

>
> I initially asked Jason who thought some of you may be interested in the
> adventure :-D
>
> Thaaaaaaaaaaaaaaaaaaaaaaaaaaank you for your thoughts ! ;-)
>
> Nathann
>
> P.S. : Oh, and if you already know of some code producing such drawings,
> please share it !
>

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org

[Nathann Cohen]

> I added a bunch to http://trac.sagemath.org/sage_trac/ticket/9136
> a few months ago. They are all nice and if I remember have nice aut gps.
> Hope they help:-)

Miam O_O
Dataaaaaaaaaaaaaaaaaaaaaaaaaaaaa O_O;;;

Thaaaaaank you ! I will train on that ! :-D

(and I am still interested by other answers)

Have fuuuuuuuuuuuuuuuuuuuuun !!!

Nathann

[Rob Beezer]

On Saturday, May 5, 2012 2:51:55 AM UTC-7, Nathann Cohen wrote:

We are currently trying to plot his graphs in some meaningful way, and his graphs are veeeerry symmetrical. Hence we would like to find a way to plot them using the information contained in their automorphism group, using some properties we think of along the way. Hence, this email : would anyone here happen to have examples of nice symmetrical graphs which have nice representations ?

Hellooooooooooo, Nathan!

Andries Brouwer has a nice collection of symmetrical graphs with interesting automorphisms groups (not too big, not too small) at:

http://www.win.tue.nl/~aeb/graphs/index.html

In Sage, I'd start with the ones below, with the ones at the bottom perhaps being the best test cases for your project.  I'll be interested to see the results of your project.   

Dima has proposed representing graphs like these in Sage with some mechanism like storing a representation of their automorphism group and representatives of orbits from the action on pairs of vertices.  Or something like that.

Rob

BuckyBall, GraphGenerators.BuckyBall
CircularLadderGraph, GraphGenerators.CircularLadderGraph
CycleGraph, GraphGenerators.CycleGraph
Grid2dGraph, GraphGenerators.Grid2dGraph
GridGraph, GraphGenerators.GridGraph
WheelGraph, GraphGenerators.WheelGraph
DodecahedralGraph, GraphGenerators.DodecahedralGraph
HexahedralGraph, GraphGenerators.HexahedralGraph
IcosahedralGraph, GraphGenerators.IcosahedralGraph
OctahedralGraph, GraphGenerators.OctahedralGraph
TetrahedralGraph, GraphGenerators.TetrahedralGraph
DesarguesGraph, GraphGenerators.DesarguesGraph
GrotzschGraph, GraphGenerators.GrotzschGraph
ShrikhandeGraph, GraphGenerators.ShrikhandeGraph
CirculantGraph, GraphGenerators.CirculantGraph
CompleteBipartiteGraph, GraphGenerators.CompleteBipartiteGraph
CompleteGraph, GraphGenerators.CompleteGraph
CubeGraph, GraphGenerators.CubeGraph
GeneralizedPetersenGraph, GraphGenerators.GeneralizedPetersenGraph
HanoiTowerGraph, GraphGenerators.HanoiTowerGraph

HeawoodGraph, GraphGenerators.HeawoodGraph
HigmanSimsGraph, GraphGenerators.HigmanSimsGraph
HoffmanSingletonGraph, GraphGenerators.HoffmanSingletonGraph
PappusGraph, GraphGenerators.PappusGraph
PetersenGraph, GraphGenerators.PetersenGraph
KneserGraph, GraphGenerators.KneserGraph
OddGraph, GraphGenerators.OddGraph

[Dima Pasechnik]

On Saturday, 5 May 2012 09:51:55 UTC, Nathann Cohen wrote:

Hellooooooooo everybody !!!

Being lost in a foreign country, my hobbies get weirder and weirder. These days I find myself playing with graph drawings because of a colleague of mine, Thomas Connor.

We are currently trying to plot his graphs in some meaningful way, and his graphs are veeeerry symmetrical. Hence we would like to find a way to plot them using the information contained in their automorphism group, using some properties we think of along the way. Hence, this email : would anyone here happen to have examples of nice symmetrical graphs which have nice representations ? What we actually need right now (besides good ideas for a plotting heuristic) is a collection of some graph to test it on. If you have some you like, could you please tell me how to build them through Sage ? If we finally get anywhere we will send you back nice pictures to get your advice on the drawings produced !

For very symmetric (say, vertex and edge-transitive) graphs a meaningful way to draw would be what is called

variously a collapsed adjacency matrix, a distance distribution diagram, etc.

That is, you take a meaningful subgroup H, like the stabilizer of a vertex, of the automorphism group, and basically create a weighted graph, with multiple arcs, with vertices being orbits of H on vertices, and joining these new vertices with bi-weighted edges;

e.g. for the Petersen graph such a diagram would look like the following:

[1]-------[3]--------[6]

     3   1    2   1    2

where an orbit of length k of H is denoted by [k], and the row of numbers below the diagram is indicating the (bi-)weights:

as follows, from left to right: there are 3 edges going from [1] to [3], there is 1 edge going from each element of [3] to [1];

there are 2 edges going from each element of [3] to [6]; there is 1 edge going from each element of [6] to [3], and finally, 

there are 3 edges going from each element of [6] to [6].

In such a way one can "draw" rather huge graphs, see e.g. p.2 of 

http://arxiv.org/pdf/math/0012266v1.pdf

Dima