I thought it would be nice to have a discussion of little pieces of Mathematica code that can help when working with graphs and networks. Here for example, one to undirect graphs when needed:

ToUndirectedGraph[dirGraph_] :=

Graph[VertexList@dirGraph, #[[1]] \[UndirectedEdge] #[[2]] & /@

Union[Sort[{#[[1]], #[[2]]}] & /@ EdgeList@dirGraph]]

or what about a graph planarity check function (i.e. adding any edge would destroy its planarity):

MaxPlanarQ[graph_] :=

PlanarGraphQ[graph] &&

With[{pos =

Select[Position[Normal@AdjacencyMatrix@graph,

0], #[[1]] < #[[2]] &],

vertex = VertexList[graph],

edges = EdgeList[graph]

},

val = True;

Do[If[PlanarGraphQ[

Graph[Append[edges,

vertex[[i[[1]]]] \[UndirectedEdge] vertex[[i[[2]]]]]]],

val = False; Break[]], {i, pos}]; Return[val]]

And one to produce random permutations for a given graph with the indicated number n of nodes:

PermuteGraph[g_, n_] :=

Table[AdjacencyMatrix@

Graph[RandomSample[VertexList@g], EdgeList@g], {n}]

What about code for counting sizes of graph automorphism groups? I have some, but it uses Saucy, an open-source software that has been tested to be (surprisingly) in practice very fast, despite the NP question underlying this task (unknown whether it has a polynomial time algorithm or it is NP-complete). There is a function in Combnatorica but you can read about its drawbacks in the

graph automorphism page in MathWorld.