Finding a subgraph of a planar graph that induces the full graph through symmetry operations Assume that we are given a (3-connected, planar, simple, and finite) graph $G$ and have calculated its automorphism group $Aut(G)$. 
Is it possible to efficiently compute a minimal connected subgraph $H$ of $G$, such that applying each of the automorphisms to it generates all of $G$, i.e., such that $Aut(G)H = G$?
If so, is it possible to choose $H$ such that it is connected? 
 A: I interpret your question as finding a minimal set of edges, such that it includes at least one edge of each edge orbit, and such that the induced graph is connected.
Clearly, the graph will be optimal if we manage to take only one edge for each orbit.
Suppose we found a set $S$ of connected edges of $k$ different orbits $O_1, ..., O_k$. Lets show that we can extend it. Take an orbit $O$ that has no edge selected. If we can find an edge of $O$ that is adjacent to an edge of $S$, we can extend $S$. Else, lets take an edge $e$ of $O$. Let $e'$ be an edge adjacent to $e$, and let $O'$ be its orbit. Clearly, each edge of $O'$ is adjacent to an edge of $O$. Because no edge of $S$ is adjacent to $O$, $O' \notin \{O_1, ..., O_k\}$. If $e'$ is adjacent to $S$, we can extend $S$, otherwise, we find a new edge adjacent to $e$ or $e'$ and so on...
Because $G$ is connected, we will eventually find an edge adjacent to $S$.
It gives you an efficient algorithm. Set $S = \{e\}$ where $e$ is an arbitrary edge, and select at each step an edge adjacent to $S$ that does belongs to an already selected orbit, until you have selected one edge for each orbit. The algorithm will succeed because you are always able to extend $S$
