7
$\begingroup$

For the other day I need to use the table of planar connected graph with few vertex. In the wolfram's mathworld , they listed only the graph with $4$ vertex.

Does anyone knows webpages or pdf on the web which carries the table of planar connected graph with up to $10$ edges?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you want to allow multiple edges, or only get the simple graphs? $\endgroup$
    – Brendan McKay
    Commented May 9, 2015 at 13:03
  • $\begingroup$ In the question the table in mathworld is simple ones, but the graphs I want to know is the planar graph that allows multiple edges, and they are visually described. $\endgroup$
    – this_is_an_apple
    Commented May 9, 2015 at 13:38

5 Answers 5

Reset to default
12
$\begingroup$

A lot depends on what the question means, in particular are the graphs simple, and is equivalence defined by embedding-preserving isomorphism or all graph isomorphisms.

For simple graphs up to general isomorphism, see my page for files up to 11 vertices.

For simple graphs up to embedding-preserving isomorphism, use plantri to make them. The command for $n$ vertices is "plantri -pc1m1 $n$", or "plantri -opc1m1 $n$" if mirror-image doesn't count as isomorphism. (At first, add "-u" to just count rather than output.) Tables up to 14 vertices are in this paper, Table 22.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What I want to know is the planar graph that allows multiple edges up to embedding-preserving isomorphism, and visually illustrated. Does anybody know the table that illustrate these graphs? $\endgroup$
    – this_is_an_apple
    Commented May 9, 2015 at 13:57
  • $\begingroup$ @this_is_an_apple If you allow multiple edges there is an infinite number of graphs even for just 2 vertices, since you can have any number of edges between them (and still be planar). $\endgroup$
    – Oliver Krüger
    Commented May 9, 2015 at 14:06
  • $\begingroup$ @this_is_an_apple such illustrated tables are included in the atlas by Jackson and Visentin I referenced above. Since you are considering planar graphs with multiple edges up to embedding-preserving isomorphism, it sounds like the objects you are interested in are precisely what are known as "planar maps". $\endgroup$
    – Noam Zeilberger
    Commented May 9, 2015 at 17:38
  • $\begingroup$ >there is an infinite number of graphs $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ To avoid the situation, I wrote "10 edges" in the question above. $\endgroup$
    – this_is_an_apple
    Commented May 10, 2015 at 2:38
4
$\begingroup$

You can generate all connected graphs with no more than 10 edges quickly using Brendan McKay's NAUTY program availible at http://pallini.di.uniroma1.it/ using (example for 11 vertices, which is maximum):

geng -c 11 0:10

and filter then using "planarg" from the same package. That is if you really mean "up to 10 edges" (not vertices). I've posted a list of all such 3386 such graphs at http://pastebin.com/P5vrZH7X (obtained in the way just described, in graph6 format).

If it is the planar connected graphs with up to 10 vertices you want you may find them at House of Graphs: http://hog.grinvin.org/Planar

Improve this answer
$\endgroup$
1
  • $\begingroup$ hog.grinvin.org/Planar#planar is exactly the page that I want to know. It costs some time to translate code into graph, but I would try it. Thank you. $\endgroup$
    – this_is_an_apple
    Commented May 9, 2015 at 13:24
2
$\begingroup$

In Sage, see www.sagemath.org, you find the algorithm

G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH-Communications in Mathematical and in Computer Chemistry, 58(2):323-357, 2007.

implemented, for which the optional package plantri needs to be installed. From the documentation:

    An iterator over connected planar graphs using the plantri generator.

    This uses the plantri generator (see [plantri]_) which is available
    through the optional package plantri.

    .. NOTE::

        The non-3-connected graphs will be returned several times, with all
        its possible embeddings.

Here are a few tests:

sage: %time len(list(graphs.planar_graphs(4)))
CPU times: user 3.23 ms, sys: 7.93 ms, total: 11.2 ms
Wall time: 21.6 ms
6

sage: %time len(list(graphs.planar_graphs(5)))
CPU times: user 11.9 ms, sys: 8.35 ms, total: 20.3 ms
Wall time: 31.9 ms
25

sage: %time len(list(graphs.planar_graphs(6)))
CPU times: user 72.5 ms, sys: 11.7 ms, total: 84.2 ms
Wall time: 96.3 ms
179

sage: %time len(list(graphs.planar_graphs(7)))
CPU times: user 920 ms, sys: 67.3 ms, total: 988 ms
Wall time: 1 s
2014

sage: %time len(list(graphs.planar_graphs(8)))
CPU times: user 19.6 s, sys: 914 ms, total: 20.5 s
Wall time: 20.6 s
31178
Improve this answer
$\endgroup$
4
  • $\begingroup$ Okay, this is neither a website nor a pdf. But you can use the website cloud.sagemath.com to generate the data... $\endgroup$
    – Christian Stump
    Commented May 9, 2015 at 12:28
  • 2
    $\begingroup$ Interestingly, plantri only needs 0.02 seconds to generate the 31178 graphs with 8 vertices. The rest must be overhead from sage to read them and make a list of them. $\endgroup$
    – Brendan McKay
    Commented May 9, 2015 at 13:28
  • $\begingroup$ That is right, I remember reading (can't find it back right now) that almost all the time is used to create Sage graphs out of the data. $\endgroup$
    – Christian Stump
    Commented May 9, 2015 at 13:46
  • $\begingroup$ That's a nice algorithm $\endgroup$
    – this_is_an_apple
    Commented May 9, 2015 at 14:01
2
$\begingroup$

Not quite an answer, but two possible sources:

(1) A003094 lists the number of unlabeled connected planar simple graphs with $n$ nodes: $$1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885, 1052805, 17449299, 313372298\;.$$

(2) Read, Ronald C., and Robin J. Wilson. An atlas of graphs. Clarendon Press, 1998. I can't access more than the table of contents of this book at the moment:

ReadWilsonCh5

Improve this answer
$\endgroup$
1
$\begingroup$

Close to what you are looking for, there is

  • An Atlas of the Smaller Maps in Orientable and Nonorientable Surfaces by David Jackson and Terry I. Visentin. (CRC press) (Google books)

This book includes tables of all of the topological maps of genus 0 with up to five edges, ordered by number of vertices (it includes many other tables as well). Note that a topological map of genus 0 can be seen as a connected planar graph with a bit of extra structure (a cyclic ordering of half-edges around each vertex).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .