[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Tamas Nepusz
Subject: Re: [igraph] planar vs. non-planar 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 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).


reply via email to

[Prev in Thread] Current Thread [Next in Thread]