graph query

[Eric W. Weisstein]

On Sun, 19 Dec 1999, Brendan McKay wrote:

> Hi Eric.
> 
> The problem is that you have a non-planar graph:
> 
>  Graph[{{0, 0, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, 
>    {1, 1, 1, 0, 1, 1}, {1, 1, 1, 1, 0, 1}, {1, 1, 1, 1, 1, 0}}, 
>   {{1., 0.}, {0.5, 0.8660254037844386}, {-0.5, 0.8660254037844386}, 
>    {-1., 0.}, {-0.5, -0.8660254037844386}, {0.5, -0.8660254037844386}}], 
> 
> You can see that the first three vertices are adjacent to the
> last three, so there is a K(3,3,) in there.

Thanks very much Brendan; I'm sorry to have troubled you.  Looks like
there's a bug in Combinatorica's PlanarQ then:

In[13]:=
PlanarQ[Graph[{{0, 0, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, {1,
         1, 1, 0, 1, 1}, {1, 1, 1, 1, 0, 1}, {1, 1, 1, 1, 1, 0}}, {{1., 
        0.}, {0.5, 0.8660254037844386}, {-0.5, 0.8660254037844386}, {-1., 
        0.}, {-0.5, -0.8660254037844386}, {0.5, -0.8660254037844386}}]]
Out[13]=
True
(not!)

Best wishes,
-Eric

--------------------------------------------------------------------
* Eric W. Weisstein                                                *
* Encyclopedist             phone:  217-398-0700 x599              *
* Wolfram Research, Inc.    FAX:    217-398-0747                   *
* 100 Trade Center Drive    e-mail: eww at wolfram.com                *
* Champaign, IL 61820-7237  WWW:    http://mathworld.wolfram.com/  *
--------------------------------------------------------------------