Combinatorica` PlanarQ not working

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 return “True” or “False”?

Answer 1

Your schedule is not a Combinatorica schedule, but rather a System schedule. You will need to explicitly specify contexts.

 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 quite a mistake. I believe Combinatorica is on the way, and I would recommend trying without it.

Answer 2

You will probably need:

 Needs["GraphUtilities`"] Needs["Combinatorica`"] cg1 = ToCombinatoricaGraph[g1]; PlanarQ[cg1] 

I do not have v8 to check.

Answer 3

Just a note, Combinatorica is on the way. However, three months ago, the Graph project guide told me that it was not planned to recompile certain algorithm interfaces, such as BrelazColoring for System Graph. Thus, some things may need Combinatorica for a while, and one way to deal with this is to try to use System'Graph for everything, save Combinatorica from the package path and go to Combinatorica functions, explicitly transforming your schedule with Combinatorica'Graph objects, calling a function Combinatorica, and then converting back to the system graph. Here are some discussions with details.

For posterity, here is the relabelGraph function, which I use to solve the ordering problem pointed out by TomD,

 relabelGraph[g_Graph,labeling_]:=Module[{vcoords,gstyle,labelMap,adjMat,newOrder,newCoords,verts}, verts=VertexList@g ; vcoords=VertexCoordinates/.AbsoluteOptions[g,VertexCoordinates]; gstyle=GraphStyle/.AbsoluteOptions[g,GraphStyle]; labelMap=Thread[Range[Length[verts]]->labeling]; adjMat=Normal@AdjacencyMatrix [g]; newOrder=Ordering[VertexList[g]/.labelMap]; newCoords=Thread[(VertexList[g]/.labelMap)->vcoords]; AdjacencyGraph[adjMat[[newOrder,newOrder]],VertexCoordinates->newCoords,GraphStyle->gstyle] ]; 

One way to use it is given below. This gives a result similar to IndexGraph , but with a sorted VertexList

 g=relabelGraph[g, Range@Length @ VertexList@g ]; 

Some of my “annoyance elimination” functions are described in graphUsage.nb in the package here

Answer 4

This is also just a note.

I want to specifically pay attention to a possible error in ToCombinatoricaGraph and a possible workaround. This may not be relevant to the original question.

In addition, I use Mma 7, so errors can be fixed in v8.

If I define a schedule as follows

 Needs["Combinatorica`"] Needs["GraphUtilities`"] gr1 = {2 -> 4, 4 -> 3, 3 -> 1} 

GraphPlot of gr1

Compare the following:

 EdgeList@gr1 EdgeList@ToCombinatoricaGraph @gr1 Edges@ToCombinatoricaGraph @gr1 

Output

 {{2, 4}, {4, 3}, {3, 1}} {{1, 2}, {2, 3}, {3, 4}} {{1, 2}, {2, 3}, {3, 4}} 

The workaround I'm using is to ignore ToCombinatoricaGraph as much as possible and instead convert to Combinatorica graph using FromOrderedPairs .

for instance

 Edges@FromOrderedPairs @ EdgeList@gr1 EdgeList@FromOrderedPairs @ EdgeList@gr1 

Output

 {{2, 4}, {4, 3}, {3, 1}} {{2, 4}, {3, 1}, {4, 3}} 

Another example: Degrees

Comparison

 Degrees@MakeSimple @ToCombinatoricaGraph[gr1] VertexList@MakeSimple @ToCombinatoricaGraph[gr1] 

Output

 {1, 2, 2, 1} {1, 2, 3, 4} 

with

 Degrees@MakeSimple @ FromOrderedPairs@EdgeList @gr1 VertexList@MakeSimple @ FromOrderedPairs@EdgeList @gr1 {1, 1, 2, 2} {1, 2, 3, 4} 

I will also give an example with Prufer codes , since here I was poorly "caught" (I did not know about SO then)

 LabeledTreeToCode@MakeSimple @ ToCombinatoricaGraph@gr1 LabeledTreeToCode@MakeSimple @ FromOrderedPairs@EdgeList @gr1 

Output

 {2, 3} {3, 4} 

(Only the second answer is true)

I reported this to Wolfram. Apparently, it is associated with reordering vertices when creating a graph on ToCombinatoricaGraph . Here is part of the answer (2009)

The reason Edges and EdgeList do not work on ToCombinatoricaGraph objects, because the Combinatorica package was developed before these functions, and the structure has not yet been adapted to work with these functions.

 Our development team is currently working to update the Combinatorica package so that these functions will be compatible. If you happen to 

run for any other questions or have any questions, please let me know.

In my opinion, ToCombinatoricaGraph should be used with caution (and avoided when possible). However, there are probably many cases (including the use given in other answers to the original question) where it does not make any difference.

Personally, I would not want to see the Combinatorica package. It contains many useful features (if very poorly documented).