Re: [igraph] planar vs. non-planar graph indices

[Tamas Nepusz]

Hi Alisa,

> In particular, I was looking at the graph.density index and  
> wondering if this calculation is for a planar or non-planar graph,  
> or does it matter?
It does not matter for this index: graph.density simply calculates the  
fraction of edges that actually exist in the network to all possible  
edges. E.g., if your graph is directed and it has 10 vertices, then  
there could theoretically be 90 edges (10*9). Therefore, a graph with  
10 vertices and 45 edges will have a density 0.5, since 45/90 = 0.5.
Theoretically one could define a "planar density" measure that takes  
into account that the vertices are laid out in 2D space and edges  
cannot cross - this limits the number of possible edges and thus  
decrease the denominator. Since I'm not familiar with planar graphs, I  
don't know if such a measure is commonly used or not. The igraph  
density measure does not care about planarity.

> Are there indices in igraph that would apply exclusively to planar  
> or non-planar graphs as the case may be?
I think there aren't any. Actually, an igraph graph object does not  
store any layout information about the vertices unless you explicitly  
assign X and Y coordinates to the vertices as vertex attributes. The  
gamma index seems similar to graph.density in igraph, and it is fairly  
easy to calculate, but it is not identical to graph.density. (At least  
if we are talking about the same gamma index, I took the definition  
from here: http://people.hofstra.edu/geotrans/eng/ch1en/meth1en/ch1m3en_2ed.html) 
. The alpha index seems more complicated due to the number of cycles  
involved, but it can be estimated (according to the above mentioned  
webpage).

--
Tamas