[igraph] Re: igraph-help Digest, Vol 21, Issue 17

[Bhalchandra Thatte]

> ------------------------------
>
> Message: 2
> Date: Mon, 28 Apr 2008 13:05:24 -0400
> From: "Alisa Coffin" <address@hidden>
> Subject: [igraph] planar vs. non-planar graph indices
> To: address@hidden

> 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.
[...]
> Tamas

Hi Alisa,

I thought I would add a comment to the explanation given by Tamas. If
an undirected graph on n vertices is planar, then it cannot have more
than 3n-6 edges. Therefore, a planar graph will have a density at most
(3n-6)/(n(n-1)/2) = 6(n-2)/(n(n-1)). But I am not sure if such a
measure will be useful to you since the converse is not true - that
is, a graph with a density smaller than the above may or may not be
planar. In other words, this measure is not sufficient to
"characterize" planarity. In general it would be difficult to find a
single number that would determine if your graph is planar or not.

> > Are there indices in igraph that would apply exclusively to planar
> > or non-planar graphs as the case may be?

Bhalchandra


-- 
Rényi Alfréd Matematikai Kutatóintézet
(Alfréd Rényi Institute of Mathematics)
Hungarian Academy of Sciences
1053 Budapest, Reáltanoda u. 13 - 15.
Tel: +36 1 483 8359
Fax: +36 1 483 8332