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

Question

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_1, H_2, \ldots, 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 maximum 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.

Answer 1

Your statement is a little ambiguous: first you write that "...such that no edge is incident between the nodes in $R$", but the next paragraph implies that there are also no edges between vertices in $A$. I'll also assume that the stars are disjoint, and that you count all edges (including those initially present in the stars). Let's also assume there are at least two stars, and at least one of them has degree $\ge 2$.

In that case, you cannot beat the $2N-4$ bound ($N$ = number of all vertices). Consider a slightly different scenario: start with any set of $N$ vertices, some red some black, at least two of each kind. At each step add arbitrarily an edge between a red and a black vertex, as long as it does not create intersections or duplicate edges. I claim that when you get stuck, all cycles have length $4$.

Your scenario is a special case of this process where you start by first creating stars and then later adding the remaining edges. If all cycles have length $4$, the $2N-4$ bound follows. More generally, it shows that no matter what bipartite graph you start from, you can always complete it to a quadrilaterated (a word I made it up) graph.

Now, let's show the claim. In this process, all paths will have alternating black and red vertices and each cycle will have length at least $4$. If the graph is not connected, you can connect any red vertex on the outer face of one component with a black vertex on the other face of another component. So we can assume the graph is already connected.

Suppose you have a face $F$ of length $6$ or more. $F$ must have at least three black vertices (some possibly equal). If some vertex $x$ is repeated on $F$, take two clockwise consecutive appearances of $x$, say $x-a-...-x-b...$. $F$ must contain a black vertex $z\neq x$, so, depending on the location of $z$, we could connect either $a$ or $b$ to $z$ inside $F$ without duplicating edges. If no vertex is repeated, pick a clockwise section $x-a-y-b-z$ of $F$, where $x,y,z$ are black and $a,b$ are red. If $x$ is connected to $b$ then $a$ cannot be connected to $z$ (by planarity), so we can add one of the edges $(x,b)$, $(a,z)$ inside $F$.