Combinatorica`PlanarQ doesn't work

Question

 g1=Graph[{UndirectedEdge[a,b]}];
 GraphQ[g1]
 (*
   OUT: True
 *)
   (*Needs["Combinatorica`"]*)
 PlanarQ[g1]
 (*
    OUT: PlanarQ[.-.]
 *)
 Combinatorica`PlanarQ[g1]
 (*
   OUT: Combinatorica`PlanarQ[.-.]
 *)

Why doesn't PlanarQ give back "True" or "False" ?

Answer 1

Your graph is not a Combinatorica graph, rather it is a System graph. You'll need to specify the contexts explicitly.

Needs["GraphUtilities`"];
g1 = System`Graph[{UndirectedEdge[a, b]}];
Combinatorica`PlanarQ[
  GraphUtilities`ToCombinatoricaGraph[g1]]

This returns True but, in general, this process is a pain and rather buggy. I believe that Combinatorica is on the way out and I'd recommend trying to get by without.

Answer 2

You probably need:

Needs["GraphUtilities`"]
Needs["Combinatorica`"]

cg1 = ToCombinatoricaGraph[g1];

PlanarQ[cg1]

I don't have v8 to check, however.