
From:  Tamas Nepusz 
Subject:  Re: [igraph] planar vs. nonplanar graph indices 
Date:  Mon, 28 Apr 2008 19:23:30 +0200 
Hi Alisa,
In particular, I was looking at the graph.density index and wondering if this calculation is for a planar or nonplanar 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 nonplanar 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
[Prev in Thread]  Current Thread  [Next in Thread] 