Message #2252

From: Roice Nelson <roice3@gmail.com>
Subject: Re: [MC4D] color graph
Date: Tue, 05 Jun 2012 13:06:19 -0500

>
> Any graph can be embedded in R3 without crossings. I believe that this one
> can’t be embedded in R2 without crossings.
>

ah, I hadn’t considered making that general statement, but it makes perfect
sense. I think you’re right about this one not being a planar
graph<http://en.wikipedia.org/wiki/Planar_graph>,
since it lives on the projective plane.

For R3 embeddings of graphs, here’s something interesting that is
reminiscent of crossings. There are some graphs that must have linked
cycles when embedded. An example is the Peterson
graph<http://en.wikipedia.org/wiki/Petersen_graph>,
which is the graph of a hemi-dodecahedron. No matter how you embed it, at
least two of the pentagonal faces will be linked.

> How does one search for a graph? That sounds super-useful!
>

Wolfram Alpha has an ever increasing library of graphs. Ed Pegg, Jr. of
mathpuzzle.com told me he and others are constantly extending that
database. You can search for things like "graph on 11
vertices<http://www.wolframalpha.com/input/?i=graph+on+11+vertices>",
and that query currently has over 500 results, names and pictures, etc. I
can’t seem to search for graphs with a particular number of vertices and
edges though, which seems like a big limitation (maybe there is a way).

Googling things like "graph with 11 vertices and 20 edges" can be helpful
as well, when you’re initially trying to find your way around. In the
past, those kinds of searches have led me to collections like this
one<http://www.win.tue.nl/~aeb/graphs/index.html>
.

I wouldn’t be surprised if there are queryable databases of graphs out
there. If anyone knows of such a thing, please do share.

seeya,
Roice