Return to Answer

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|=6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ exist with $e=6v-12$ (or at least, I know of such an example for $v=12$). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|\ge 6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ exist with $e=6v-12$ (or at least, I know of such an example for $v=12$). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|=6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ with $e=6v-14$ could in principle exist (I asked a question about it). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|=6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ exist with $e=6v-12$ (or at least, I know of such an example for $v=12$). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|=6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ exist with $e=6v-12$ (or at least, I know of such an example for $v=12$). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.

Disclaimer. This answer does not solve the problem. I decided it is probably more useful to keep my answer here, but please know it is just a long comment.

Notation. For a graph $(V,E)$, we call $e=|E|, v=|V|$.

In a planar graph, we have a maximum number of edges: $e\leq 3v-6$ if $v\geq 3$. Thus, for a graph of thickness $2$, we have the trivial upper bound $$ e\leq 6v-12. $$

Proposition 1. Let $(V,E)$ be a graph with thickness* $2$ and such that $e\in\{6v-14,6v-13,6v-12\}$. Then for any decomposition $E=E_1\cup E_2$ such that the graphs $(V,E_1),(V,E_2)$ are planar, the two are also connected.

*Remark. As you can check from the proof, the proposition is true for both the geometric thickness and the “normal” thickness.

Proof. To see that, assume you decompose $E=E_1\cup E_2$. Since $(V,E_i)$ must be planar graphs (and $v\geq 5$), we have $$|E_i|\leq 3|V|-6$$ Since $|E|=6|V|-14$ and $|E_1|+|E_2|=|E|$, it follows that $$ |E_i|\geq 3|V|-8. $$ Now, I claim that the two subgraphs cannot be disconnected. In fact, to any disconnected planar graph with $v\geq 4$ you can add at least three edges while still keeping it planar (the main reason is that any face of a planar graph has at least three vertices). But if you add three edges to $E_i$ you make it exceed the maximum number of edges for a planar graph, so both $(V,E_1)$ and $(V,E_2)$ must be connected.

Note that such a graph would require at least $v\geq 11$, since for $6v-14\leq {n\choose 2}\iff n\geq 11 \text{ or } n\leq 2$.

Edit 1. Thanks to the nice remark of Alex Ravsky, we know that such a graph cannot exist with geometric thickness $2$, although graphs with “normal” thickness $2$ with $e=6v-14$ could in principle exist (I asked a question about it). In particular we can say something about a graph like the one in Proposition 1.

Lemma 2. Assume $(V,E)$ is a graph with $e=6v-12-c$, $c\in\mathbb N$. Then, in any representation of the graph in $\mathbb R^2$ where edges are not necessarily straight lines and such that $E$ can be written as a disjoint union of planarly embedded graphs, the number of edges $e’$ that do not intersect with any other edge is at most $c$.

Proof. As from the comment of Alex Ravsky, call $E’$ the set of edges that do not cross other edges, and call $E’’$ the set of remaining edges. Then write $E’’=E’’_1\cup E’’_2$ such that $E_i’’$ are planarly embedded. Then, $E’\cup E’’_i$ are also planarly embedded, in particular $$ |E’’_i|+|E’|\leq 3|V|-6. $$ This leads to $$ |E|+|E’|\leq 6|V|-12, $$ which proves the Proposition.

Corollary 3. Any graph with geometric thickness $2$ satisfies $e\leq 6v-15$.

Proof. The convex hull of the graph cannot have edges that intersect with other edges, and it is made of at least $3$ edges.