About generalized planar graphs and generalized outerplanar graphs

Question

Any planar, respectively, outerplanar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$,
respectively, $|E'|\le 2|V'|-3$, for every subgraph $G'=(V',E')$ of $G$.
Also, (outer-)planar graphs can be recognized in polynomial time.

What is known about graphs $G=(V,E)$ such that $|E'|\le 3|V'|-6$ (resp. $|E'|\le 2|V'|-3$) for every subgraph $G'=(V',E')$ of $G$? Is it possible to recognize them in polynomial time?

Edit (after Eppstein's nice answer): Any planar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$ for every subgraph $G'=(V',E')$ of $G$ with at least three vertices $|V'|\ge 3$. So, "generalized planar graphs" would be those satisfying this property, and recognizing them in polynomial time seems to be an (interesting) open question.

Answer 1

In the notation of Lee and Streinu (citation below) the second class you list are the (2,3)-sparse graphs. They give an algorithm to test whether a graph is (k,l)-sparse in polynomial time. However, the situation with planar graphs and $|E'|\le 3|V'|-6$ is a little more complicated, because that inequality is not true for all sets of vertices (if it were true, no two vertices could be connected by an edge, because $3\cdot 2-6=0$). So the class of (3,6)-sparse graphs (in their notation) consists only of empty graphs. Probably their algorithms can be extended to graphs for which the inequality holds for all sets of more than two vertices.

Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics 308 (8): 1425–1437, doi:10.1016/j.disc.2007.07.104, arxiv:math/0702129.

Answer 2

What is known about "generalized outerplanar graphs" or (2,3)-sparse graphs? Some additional facts to DavidEppstein's answer:

In 1982, in this paper (Corollaries 1 and 2), Lovász and Yemini characterized generalized outerplanar graphs (in their notation, generic independent graphs) as those graphs $G$ having the property that doubling any edge of $G$ results in a graph which is the edge-disjoint union of two forests.

Very previously, in 1970, Henneberg and Laman proved that generalized outerplanar graphs can be recursively obtained from $K_2$ by three so-called Henneberg moves (adding a degree-1 vertex, adding a degree-2 vertex, and a certain kind of adding a degree-3 vertex).

These characterizations give the first polynomial recognitions for generalized outerplanar graphs.

Some remarks related to generalized planar graphs can be found in the last section of this paper. I think, characterizing and recognizing generalized planar graphs still remain very interesting open questions.