4
$\begingroup$

Given $n$ vertices of color $1$ and m vertices of color $2$, what is the maximal number of edges that can join them on the constraints - $(a)$ no edge joins has the same color ends and $(b)$ no two edges intersect when drawn on a plane (a planar graph)?

Also given such $n$, $m$ how many such graphs can be generated so that no vertex is isolated and how many maximal non-equivalent maximal graphs are possible?

Are these standard questions that have been studied anywhere?

$n = m$ is the case I am looking for a lead.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Presumably "again" refers to your earlier question: cstheory.stackexchange.com/questions/5331/… $\endgroup$
    – Dave Clarke
    Mar 10, 2011 at 18:41
  • $\begingroup$ Yes. But the older one asks for explicit construction. This one seems outwardly simpler!! $\endgroup$
    – Turbo
    Mar 10, 2011 at 18:42
  • 4
    $\begingroup$ Next time, please provide the necessary link(s) by yourself rather than relying on the moderators doing the task for you. $\endgroup$
    – Tsuyoshi Ito
    Mar 10, 2011 at 20:45

1 Answer 1

Reset to default
15
$\begingroup$

If $\min(m,n)=1$, the maximum number of edges in a planar bipartite graph with $m$ vertices on one side of the bipartition and $n$ on the other side is $m+n-1$ (just connect them in a star). Otherwise, the maximum number is $2(m+n)-4$.

The upper bound (any bipartite planar graph with $V$ vertices has at most $2V-4$ edges) follows by combining Euler's formula $V-E+F=2$ with the observation that all faces have at least four edges, and each edge belongs to at most two faces, so $E\ge 2F$. Use this inequality to eliminate $F$ from Euler's formula and you get $E\le 2V-4$.

For the lower bound, choose two vertices from the side with $m$ vertices and form a complete bipartite graph $K_{2,n}$ with $2n$ edges. Then, choose one of the quadrilateral faces of this graph and place the remaining $m-2$ vertices into it, connecting each one to both of the vertices of the other color within the same face, adding $2(m-2)$ more edges.

As for the number of distinct maximal planar bipartite graphs on this many vertices, I don't know, but it's certainly some kind of exponential.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.