Bounding the number of edges between star graphs such that graph is planar

I have a graph G which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let H₁, H₂,…,H_n be different star graphs of different sizes which are present in G. We call the set of all nodes which are centres in any star graph R.

Now suppose these star graphs are building edges to other star graphs such that no edge is incident between any nodes in R. Then, how many edges exist at maxim开发者_开发百科um between the nodes in R and the nodes which are not in R, if the graph should remain planar?

I want the upper bound on the number of such edges. One upper bound that I have in mind is: consider them as bipartite planar graph where R is one set of vertices and rest of the vertices form another set A. We are interested in edges between these sets (R and A). Since it is planar bipartite, the number of such edges is bounded by twice the number of nodes in G.

What I feel is that is there a better bound, maybe twice the nodes in A plus the number of nodes in R.

In case you can disprove my intuition, then that would also be good. Hopefully some of you can come up with a good bound along with some relevant arguments.

---

That's the best you can do. Take any planar graph G and construct its face-vertex incidence graph H, whose faces all have 4 edges. Let R be the set of faces of G and construct stars any which way using edges in H. This achieves the bound for bipartite planar graphs.