1
$\begingroup$

My question may be similar to generating-21-vertex-4-regular-plane-graphs-with-8-faces-of-degree-3-and-15-face., but it has differences. The plane graphs I desire (without needing regularity) have only two 3-faces, while all other faces are 4-faces.

Brinkmann and McKay's program plantri can generate planar quadrangulations, which are planar graphs with all faces of size 4. The plane graphs I desire are very close to them, yet different.

Are there currently any tools available to obtain all these graphs?

P.S. Constructing several examples is something I can do. For instance, I can start by a quadrangulation and then remove an edge. In addition, there are other construction methods, such as in the graph below, where the two triangles do not share any common vertices.

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The conditions "max face = 4, 21 edges, 12 vertices" characterize them. So:

plantri -pf4e21 12 -- 125 outputs (these are the 3-connected ones)

plantri -pf4e21c2 12 -- 120857 outputs (these are the 2-connected ones)

There are none which are connected but not 2-connected.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .