The most general method would be to successively expand a connected, planar, bipartite graph $G$, whose vertices are colored $purple$ and $orange$ in a manner that makes each edge adjacent to a $purple$ and an $orange$ vertex.
In every step, $G$ can be expanded by either:

• adding a vertex that is connected to $G$ via an edge and colored in a way that makes the newly added edge adjacent to two different colors

or

• by adding adding an edge not yet in the graph that would connect vertices of different color and, that would preserve planarity.

As the planarity of graphs can be checked efficiently, (see e.g. http://en.wikipedia.org/wiki/Planarity_testing) it is viable to determine in each step a set of candidate edges, whose insertion into $G$ would preserve planarity; the bipartitness is ensured by inserting only edges that would connect vertices of different color.

A basic, purely "topological" method could then be to expand the graph by first checking if the set of candidate edges for insertion, while preserving planarity and bipartitness, is empty;

if that is the case, the only option is to

• add a new vertex to the graph, restore the graph's connectivity and color the newly added vertex appropriately

else roll dice whether to expand the graph via adding a new vertex as described above or whether to

• add a randomly selected edge from the candidate set and to

• redetermine the set of candidate edges by removing from it those edges, whose insertion would violate the planarity condition.

The selection of the vertex, to which a new vertex will be connected, or, which of the candidate edges will be selected, can e.g. be controlled by probabilities that depend on vertex degrees; also the decision whether to add a vertex or an edge, can be controlled by assigning a certain probability to the options.
If fluffy graphs are preferred, then the insertion of a new vertex should have higher probability than inserting one of the candidate edges.

The most general method would be to successively expand a connected, planar, bipartite graph $G$, whose vertices are colored $purple$ and $orange$ in a manner that makes each edge adjacent to a $purple$ and an $orange$ vertex.
In every step, $G$ can be expanded by either:

• adding a vertex that is connected to $G$ via an edge and colored in a way that makes the newly added edge adjacent to two different colors

or

• by adding adding an edge not yet in the graph that would connect vertices of different color and, that would preserve planarity.

As the planarity of graphs can be checked efficiently, (see e.g. http://en.wikipedia.org/wiki/Planarity_testing) it is viable to determine in each step a set of candidate edges, whose insertion into $G$ would preserve planarity; the bipartitness is ensured by inserting only edges that would connect vertices of different color.

A basic, purely "topological" method could then be to expand the graph by first checking if the set of candidate edges for insertion, while preserving planarity and bipartitness, is empty;

if that is the case, the only option is to

• add a new vertex to the graph, restore the graph's connectivity via a single edge and color the newly added vertex appropriately

• update the set of candidate edges by adding to it those edges that would be adjacent to the newly added vertex and, adjacent to another vertex of different color.

else roll dice whether to expand the graph via adding a new vertex as described above or whether to

• add a randomly selected edge from the candidate set and to

• redetermine the set of candidate edges by removing from it those edges, whose insertion would violate the planarity condition.

The selection of the vertex, to which a new vertex will be connected, or, which of the candidate edges will be selected, can e.g. be controlled by probabilities that depend on vertex degrees; also the decision whether to add a vertex or an edge, can be controlled by assigning a certain probability to the options.
If fluffy graphs are preferred, then the insertion of a new vertex should have higher probability than inserting one of the candidate edges.

The most general method would be to successively expand a connected, planar, bipartite graph $G$, whose vertices are colored $purple$ and $orange$ in a manner that makes each edge adjacent to a $purple$ and an $orange$ vertex.
In every step, $G$ can be expanded by either:

• adding a vertex that is connected to $G$ via an edge and colored in a way that makes the newly added edge adjacent to two different colors

or

• by adding adding an edge not yet in the graph that would connect vertices of different color and, that would preserve planarity.

As the planarity of graphs can be checked efficiently, (see e.g. http://en.wikipedia.org/wiki/Planarity_testing) it is viable to determine in each step a set of candidate edges, whose insertion into $G$ would preserve planarity; the bipartitness is ensured by inserting only edges that would connect vertices of different color.

A basic, purely "topological" method could then be to expand the graph by first checking if the set of candidate edges for insertion, while preserving planarity and bipartitness, is empty;

if that is the case, the only option is to

• add a new vertex to the graph, restore the graph's connectivity and color the newly added vertex appropriately

else roll dice whether to expand the graph via adding a new vertex as described above or whether to

• add a randomly selected edge from the candidate set and to

• redetermine the set of candidate edges by removing from it those edges, whose insertion would violate the planarity condition.

The selection of the vertex, to which a new vertex will be connected, or, which of the candidate edges will be selected, can e.g. be controlled by by probabilities that depend on vertex degrees; also the decision whether to add a vertex or an edge, can be controlled by assigning a certain probability to the options.
If fluffy graphs are preferred, then the insertion of a new vertex should have higher probability that inserting one of the candidate edges.

The most general method would be to successively expand a connected, planar, bipartite graph $G$, whose vertices are colored $purple$ and $orange$ in a manner that makes each edge adjacent to a $purple$ and an $orange$ vertex.
In every step, $G$ can be expanded by either:

• adding a vertex that is connected to $G$ via an edge and colored in a way that makes the newly added edge adjacent to two different colors

or

• by adding adding an edge not yet in the graph that would connect vertices of different color and, that would preserve planarity.

As the planarity of graphs can be checked efficiently, (see e.g. http://en.wikipedia.org/wiki/Planarity_testing) it is viable to determine in each step a set of candidate edges, whose insertion into $G$ would preserve planarity; the bipartitness is ensured by inserting only edges that would connect vertices of different color.

A basic, purely "topological" method could then be to expand the graph by first checking if the set of candidate edges for insertion, while preserving planarity and bipartitness, is empty;

if that is the case, the only option is to

• add a new vertex to the graph, restore the graph's connectivity and color the newly added vertex appropriately

else roll dice whether to expand the graph via adding a new vertex as described above or whether to

• add a randomly selected edge from the candidate set and to

• redetermine the set of candidate edges by removing from it those edges, whose insertion would violate the planarity condition.

The selection of the vertex, to which a new vertex will be connected, or, which of the candidate edges will be selected, can e.g. be controlled by probabilities that depend on vertex degrees; also the decision whether to add a vertex or an edge, can be controlled by assigning a certain probability to the options.
If fluffy graphs are preferred, then the insertion of a new vertex should have higher probability than inserting one of the candidate edges.