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

<p>In 1982, in <a href="http://epubs.siam.org/doi/abs/10.1137/0603009">this paper</a>
(Corollaries 1 and 2), Lovász and Yemini characterized generalized
outerplanar graphs (in their notation, <em>generic independent graphs</em>) 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.</p>

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

<p>These characterizations give the first polynomial recognitions for generalized
outerplanar graphs.</p>

<p>Some remarks <em>related</em> to generalized planar graphs can be found in the last section
of <a href="http://www.sciencedirect.com/science/article/pii/0166218X84900799">this paper</a>.
I think, characterizing and recognizing generalized planar graphs still
remain very interesting open questions.</p>

CC BY-SA 3.0
2013-08-03T14:37:18.937Z
2013-08-03T14:44:17.113Z
2013-08-03T14:44:17.113Z
user13136
<p>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.</p>

<p>Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics 308 (8): 1425–1437, <a href="http://dx.doi.org/10.1016/j.disc.2007.07.104">doi:10.1016/j.disc.2007.07.104</a>, <a href="http://arxiv.org/abs/math/0702129">arxiv:math/0702129</a>.</p>

CC BY-SA 3.0
2013-08-01T00:23:30.453Z
2013-08-01T00:31:55.440Z
2013-08-01T00:31:55.440Z
David Eppstein
<p>Any <a href="http://en.wikipedia.org/wiki/Planar_graph">planar</a>, respectively, <a href="http://en.wikipedia.org/wiki/Outerplanar_graph">outerplanar graph</a> $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$,<br>
respectively, $|E'|\le 2|V'|-3$, for every subgraph $G'=(V',E')$ of $G$.<br>
Also, (outer-)planar graphs can be recognized in polynomial time.</p>

<p>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?</p>

<p><strong>Edit</strong> (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$ <em>with at least three vertices</em> $|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. </p>

CC BY-SA 3.0
2013-08-03T19:48:03.033Z
By your question and edit, I changed the title; feel free to roll back.
user13136
<reference-request><graph-theory><graph-algorithms>
About generalized planar graphs and generalized outerplanar graphs
Tobias Müller
# About generalized planar graphs and generalized outerplanar graphs

(Asked by: username_0 on 2013-07-31)

Any [planar](http://en.wikipedia.org/wiki/Planar_graph), respectively, [outerplanar graph](http://en.wikipedia.org/wiki/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.

**Tags:** reference-request, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: By your question and edit, I changed the title; feel free to roll back.  

---

## 2 answers

### Answer by username_2 on 2013-08-01. Score: 16 | Accepted answer

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](http://dx.doi.org/10.1016/j.disc.2007.07.104), [arxiv:math/0702129](http://arxiv.org/abs/math/0702129).


---

### Answer by username_1 on 2013-08-03. Score: 13

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

In 1982, in [this paper](http://epubs.siam.org/doi/abs/10.1137/0603009)
(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](http://www.sciencedirect.com/science/article/pii/0166218X84900799).
I think, characterizing and recognizing generalized planar graphs still
remain very interesting open questions.


---

