GRAFFITI
Mathematical Graphs, with Embedding Information

GRAFFITI is a dataset directory which contains 195 mathematical graphs, described as a collection of nodes, with edges between some pairs of nodes.

The description of each graph includes an "embedding", that is, an assignment of (X,Y) coordinates to each node, so that a plot of the graph can be made.

The files defining each graph are in the GRF file format.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

GRAPH_REPRESENTATION, a data directory which contains various representations of abstract mathematical graphs.

GRF, a data directory which contains examples of GRF files, an abstract graph file format, 2D graphics;

GRF_DISPLAY, a MATLAB program which reads a GRF file defining a mathematical graph and displays it in the MATLAB graphics window.

GRF_DISPLAY_OPENGL, a C++ program which reads a GRF file defining a mathematical graph and displays it in an OpenGL graphics window.

GRF_IO, a C++ library which reads or writes a GRF file;

GRF_IO, a FORTRAN90 library which reads or writes a GRF file;

GRF_IO, a MATLAB library which reads or writes a GRF file;

GRF_TO_EPS, a FORTRAN90 program which converts a GRF file to EPS forma;

GRF_TO_XYL, a FORTRAN90 program which converts information describing the adjacency and embedding of an abstract graph from GRF to XYL format.

Datasets:

• graff001.grf, K1.
• graff002.grf, the cycle on five vertices and so can be constructed. The circular drawing is the minimum energy configuration for the spring embedding heuristic.
• graff003.grf, two disconnected vertices. Thus it can be constructed.
• graff004.grf, the empty graph on three vertices.
• graff005.grf, four disconnected copies of K_2, embedded as a bipartite graph.
• graff006.grf, the cycle on 29 vertices
• graff007.grf, the cycle on 28 vertices.
• graff008.grf, this circular drawing of graph number 8 is not too enlightening as to its structure.
• graff009.grf, more information will be necessary to provide a reasonable drawing.
• graff010.grf, more information will be necessary to provide a reasonable drawing.
• graff011.grf, an example of a circulant graph.
• graff012.grf, K2, a path on two vertices.
• graff013.grf, K5, the smallest nonplanar graph.
• graff014.grf, K11. Complete graphs and cycles are circulant graphs.
• graff015.grf, the Petersen graph, which is the only three-regular graph of girth 5. The spring embedding does a decent, but not perfect job of showing its structure.
• graff016.grf, of order 64, is too dense for individual edges to appear in displaying its circular embedding. In this case, the complement of the graph is much more informative.
• graff017.grf, Even cycles are bipartite graphs, and this drawing reflects that.
• graff018.grf, a simple cycle on six vertices.
• graff019.grf, a simple cycle on seven vertices.
• graff020.grf, is bipartite, but not regular.
• graff021.grf, is bipartite, but not regular.
• graff022.grf, seems to be K{10,10} less several edges.
• graff023.grf, is the cycle on eight vertices.
• graff024.grf, is a tree on eight vertices. RadialEmbedding has been used to draw the tree so no two edges cross.
• graff025.grf, is a tree on 14 vertices. Again, RadialEmbedding has been used to draw the tree so no two edges cross.
• graff026.grf, has been fed to SpringEmbedding, but it is not at all clear what is going on.
• graff027.grf, is the triangle, or K_3.
• graff028.grf, defines the path on seven vertices, or Path[7].
• graff029.grf, can be constructed by GraphJoin[ EmptyGraph[2], EmptyGraph[3] ].
• graff030.grf, s the complete bipartite graph K_{5,5}.
• graff031.grf, is the circulant graph CirculantGraph[13, {1,5}].
• graff032.grf, is another circulant graph, CirculantGraph[13, {2,3,4,6}].
• graff033.grf, is the star on eleven vertices Star[11].
• graff034.grf, represents K_{10}.
• graff035.grf, is pretty unimpressive under the spring heuristic.
• graff036.grf, consists of K_8 with one vertex incident on path of length two.
• graff037.grf, has two K_4's joined with an isolated vertex, and can be constructed GraphJoin[K[1], GraphUnion[2,K[4]]].
• graff038.grf, is the circulant graph CirculantGraph[6,{1,2}].
• graff039.grf, is a tree with four vertices of degree 1, two of degree 3, and seven of degree 2.
• graff040.grf, is disconnected, GraphUnion[ EmptyGraph[2], K[2] ].
• graff041.grf, is interesting, if not immediately enlightening. An extra vertex is attached to each of the leaves of Star[11].
• graff042.grf, is the circulant graph CirculantGraph[12,{1,2,3}].
• graff043.grf, is a terrible drawing of DeleteEdge[K[4],{1,2}].
• graff044.grf, is a simple path on three vertices.
• graff045.grf, is a simple path on four vertices.
• graff046.grf, is a terrible drawing of DeleteEdge[K[5],{1,2}].
• graff047.grf, is a cycle of length four, with an edge to an isolated vertex.
• graff048.grf, is two cycles of length four sharing one vertex between them.
• graff049.grf, is a path of length three with both endpoints joined to K_3.
• graff050.grf, is \oi{GraphJoin[K[1], K[3,3]]}.
• graff051.grf, is GraphUnion[K[1],K[4]]. The spring embedding heuristic causes disconnected components to drift apart.
• graff052.grf, is the circulant graph CirculantGraph[10,{1,2,3,4}].
• graff053.grf, is fairly well illustrated by the spring embedding heuristic.
• graff054.grf, is a nicely drawn tree.
• graff055.grf, is a tree with a high degree of symmetry.
• graff056.grf, is a bipartite planar graph.
• graff057.grf, is the union of three even cycles, GraphUnion[Cycle[4], GraphUnion[Cycle[6],Cycle[8]] ].
• graff058.grf, is an odd cycle with two isolated vertices attached on one cycle vertex.
• graff059.grf, looks like K[10,10].
• graff060.grf, has an interesting circular embedding.
• graff061.grf, is another tree.
• graff062.grf, is K_{8,2} minus one edge.
• graff063.grf, is K_{7,2} with one extra vertex and edge.
• graff064.grf, is GraphJoin[K[7],EmptyGraph[2]], and with this drawing looks almost three-dimensional.
• graff065.grf, The structure of graph number 65 is not clear from this drawing.
• graff066.grf, is the complete bipartite graph K_{3,4}.
• graff067.grf, looks like GraphJoin[K[1], K[8]]. but I believe some edges are obscured by the center vertex.
• graff068.grf, has two edges deleted from K_{2,12}.
• graff069.grf, The spring embedding heuristic does a good job showing the symmetry of graph number 69.
• graff070.grf, is a simple tree.
• graff071.grf, is a tree with a longer tail than graph number 70.
• graff072.grf, is a tree with branches consisting of paths on 1, 2, and 3 vertices.
• graff073.grf, has trouble because its embedding had points too close to zero.
• graff074.grf, looks like K_{10} entended by paths on length one, and in one case two.
• graff075.grf, is too dense for its circular embedding to reveal any structure. The complement appears sparser, but it still not understood.
• graff076.grf, is two edges removed from being a regular graph.
• graff077.grf, is the tree Path[29].
• graff078.grf, appears to be two K_{10}'s connected by a path of nine other vertices.
• graff079.grf, is spectacular, whatever it is!
• graff080.grf, is a tree, and so might be better displayed with a radial embedding.
• graff081.grf, appears similar to graph number 78, but is larger.
• graff082.grf, has several clusters of vertices attached to a central path.
• graff083.grf, is another interesting structure but not well understand.
• graff084.grf, The spring embedding of graph number 84 put several vertices too close together.
• graff085.grf, is a tree consisting of stars of 13 and 14 vertices joined at the center.
• graff086.grf, is a path with two cliques dense enough to look ugly.
• graff087.grf, is too dense to be properly displayed in a circular embedding.
• graff088.grf, does not appear to be symmetric, at least from this drawing.
• graff089.grf, looks like it might be a large circulant graph.
• graff090.grf, does not look like a circulant graph, but is quite symmetric.
• graff091.grf, is a tree similar to graph 80.
• graff092.grf, is too dense to properly identify.
• graff093.grf, appears to be a tree.
• graff094.grf, might be a tree similar to graph number 94.
• graff095.grf, is not a tree, which means the previous graphs may not be.
• graff096.grf, continues this trend.
• graff097.grf, contains few cycles.
• graff098.grf, is a cycle on 12 vertices with edges to two additional vertices.
• graff099.grf, is a cycle on fifteen vertices, each of which is connected to a vertex of degree one.
• graff100.grf, seems to be similar to graph number 99, with the cycle replaced by K_{15}.
• graff101.grf, looks like a comb with a little K_4 at the end.
• graff102.grf, is open on one end.
• graff103.grf, resembles a convex polyhedra in this drawing, which means that is it planar.
• graff104.grf, is bipartite, but symmetric enough to suggest that this is not the right embedding.
• graff105.grf, seems to be a product graph.
• graff106.grf, is in the tradition of graphs 94 to 96.
• graff107.grf, looks like another path with loops on the ends.
• graff108.grf, The symmetry of graph number 108 is evident in this spring embedding.
• graff109.grf, consists of two copies of some graph joined in some way.
• graff110.grf, consists of three copies of some graph joined in some way.
• graff111.grf, is K_{2,5}.
• graff112.grf, is K_{3,3} less an edge.
• graff113.grf, is a simple tree.
• graff114.grf, is not K_{4,4} but an incredible simulation.
• graff115.grf, is another path with two loops at the end.
• graff116.grf, is the same flavor as graph number 115.
• graff117.grf, is the star Star[32].
• graff118.grf, is the cycle on 30 vertices.
• graff119.grf, is the cycle on 31 vertices
• graff120.grf, is the cycle on 29 vertices.
• graff121.grf, is a path on 30 vertices.
• graff122.grf, is another dense graph with protrusions.
• graff123.grf, is bipartite and symmetrical.
• graff124.grf, is GraphJoin[K[1],Cycle[4]].
• graff125.grf, is two components highly connected.
• graff126.grf, is an edge and vertex added to \oi{Cycle[10]}.
• graff127.grf, is two cycles sharing an edge, and nicely displayed as a spring embedding.
• graff128.grf, is a cycle with two cross-edges.
• graff129.grf, looks like another circulant graph.
• graff130.grf, is not K_4, since it contains 16 vertices.
• graff131.grf, is too dense to identify from this drawing.
• graff132.grf, is two components joined in a star.
• graff133.grf, is the circulant graph CirculantGraph[10,{1,4,5}].
• graff134.grf, is GraphUnion[2,K[3]].
• graff135.grf, is GraphUnion[5,Cycle[5]].
• graff136.grf, is a triangle with a tail.
• graff137.grf, is the union of disjoint cycle of length 6, 10, and 14.
• graff138.grf, is three triangles and a K_2 with a vertex in common.
• graff139.grf, is a cycle on four vertices.
• graff140.grf, is K_{3,2} less an edge.
• graff141.grf, is a nice circulant graph.
• graff142.grf, is too dense to identify from this picture, but it looks like a circulant graph.
• graff143.grf, is two stars whose centers are on a triangle.
• graff144.grf, is a generalization of graph 143.
• graff145.grf, is the path on three vertices.
• graff146.grf, is clearly shown in this spring embedding.
• graff147.grf, is less clearly illustrated by the spring embedding.
• graff148.grf, is even less clearly illustrated by the spring embedding.
• graff149.grf, is too dense to really understand from this drawing.
• graff150.grf, is sparse enough to understand.
• graff151.grf, should not be drawn in such a two-dimensional manner.
• graff152.grf, is sparse enough that a better embedding might be understandable.
• graff153.grf, consists of two large stars joined at the centers.
• graff154.grf, might be clearer with a better drawing.
• graff155.grf, is GraphUnion[2,Star[6]].
• graff156.grf, is GraphUnion[Cycle[4],Cycle[5]].
• graff157.grf, is the circulant graph CirculantGraph[7,{2,3}].
• graff158.grf, is GraphUnion[K[2],K[3]].
• graff159.grf, is GraphUnion[2,K[3]].
• graff160.grf, is GraphUnion[K[1],K[2]].
• graff161.grf, is Star[53].
• graff162.grf, is not a cycle, but has a dense set of interconnections to its neighborhood.
• graff163.grf, is similar to the above, but with a thicker neighborhood.
• graff164.grf, Since graph number 164 the largest graph in the collection, an almost complete graph on 144 vertices, we display its complement instead.
• graff165.grf, is a ring but not a cycle.
• graff166.grf, is the path on 90 vertices.
• graff167.grf, appears in the tradition of graph number 122.
• graff168.grf, is bipartite, but otherwise indistinguishable.
• graff169.grf, is GraphUnion[ GraphUnion[7,K[2]], GraphUnion[2, Star[6]] ].
• graff170.grf, is GraphUnion[K[2], GraphUnion[2,Cycle[4]]].
• graff171.grf, is dense, but has a clearly identifiable structure.
• graff172.grf, is a regular-looking structure with some attachments.
• graff173.grf, seems to be two vertices of degree n-1 and n-2 vertices of degree two.
• graff174.grf, is another dense graph with attachments.
• graff175.grf, is another fairly dense graph.
• graff176.grf, is a cycle on four vertices.
• graff177.grf, is an eight vertex component unioned with EmptyGraph[2].
• graff178.grf, is a cycle of length four with an attached path of length two.
• graff179.grf, is like graph number 178 with an attached path of length three.
• graff180.grf, is like graph number 178 with an attached path of length four.
• graff181.grf, is GraphUnion[ Cycle[5], K[2] ].
• graff182.grf, is the union of GraphUnion[6,K[2]]} and \oi{Cycle[5].
• graff183.grf, is two 4-cycles sharing one vertex. Didn't this one occur earlier?
• graff184.grf, is properly drawn using the spring embedding heuristic.
• graff185.grf, is GraphUnion[K[1], K[2]]. Didn't this one occur earlier?
• graff186.grf, has fifteen vertices overall.
• graff187.grf, is another large dense graph.
• graff188.grf, is another disconnected graph.
• graff189.grf, looks like graph number 187.
• graff190.grf, is at least small enough that the spring embedding heurstic can be applied.
• graff191.grf, looks like it will prosper with a different embedding.
• graff192.grf, also looks like it has possibilities.
• graff193.grf, looks like a candidate for the graph editor.
• graff194.grf, is another black hole.
• graff195.grf, is another ugly to end this exercise.

You can go up one level to the DATASETS directory.