A **vertex-edge flag** in a graph is a vertex together with an edge incident to that vertex. Given a graph $\Gamma$ embedded in a compact oriented surface $S$, when does the group of homeomorphisms of $S$ act transitively on vertex-edge flags of $\Gamma$?

We can start by looking a graphs embedded in the sphere, and start among those by looking at graphs that consist of the vertices and edges of a convex polyhedron. Among these, the obvious examples on which *isometries* act transitively on vertex-edge flags are the 5 Platonic solids. However, there are also two Archimedean solids with this property, namely the cuboctahedron:

and the icosidodecahedron:

I believe these are all the convex polyhedra on which isometries act transitively on vertex-edge flags. A polyhedron is said to be **isotoxal** if isometries act transitively on *edges*. There are 9
isotoxal convex polyhedra, and among these I see 7 on which isometries act transtively on vertex-edge flags: the 5 Platonic solids and the 2 shown above.

There are also infinitely many other connected graphs embedded in the sphere on which isometries act transitively on vertex-edge flags, namely the hosohedra, like this:

and the dihedra, like this:

I believe these are all the *connected* graphs embedded in the sphere on which *isometries* acts transitively on vertex-edge flags. If we consider graphs embedded in the sphere that are *not* connected, we get a host of other examples: for example, a bunch of equal-sized regular $n$-gons embedded in the sphere. If we further drop the requirement that the homeomorphisms be isometries, we get even more examples: for example, a bunch of copies of the complete graph on 4 vertices embedded in the sphere. I am happy to restrict attention to connected graphs, to avoid such clutter.

I am also happy to omit graphs that have self-loops.

So, here is a sub-question that interests me: *what are all the connected graphs without self-loops embedded in the sphere on which homeomorphisms of the sphere act transitively on vertex-edge flags?* Have I listed them all, or are there more?

(Whoops, here are some more: the empty graph, the graph with one vertex and no edges, and the graph with two vertices and one edge connecting them. The last might be considered a degenerate hosohedron.)

When we go to higher genus the situation becomes a lot more complicated and interesting. For example, in genus 3 we have Klein's quartic curve tiled by 56 triangles meeting 7 at each vertex:

So, I'd be perfectly happy to hear classifications that only handle surfaces of genus less than some fixed value.