Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Re added the example, which now works
Source Link

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.


Example for $v=12$

An example of such a graph with thickness $2$ with $|V|=12$ is the following.

$$ V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\}, $$ $$ E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,i’)|1\leq i\leq 5\}. $$$$ E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,j’)|1\leq i,j\leq 5, j-i= 3\mod 5\}. $$ We note that $|E|={12\choose 2}-6=60=6|V|-12$, which is the theoretical upper bound for thickness $2$ graphs. We can decompose $E$ into $$ E=E_1\cup E_2, $$ $$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=1\text{ or }2\mod 5\}, $$$$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }1\mod 5\}, $$ $$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }3\mod 5\}. $$$$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=2\text{ or }4\mod 5\}. $$ Then, $G_1=(V,E_1),G_2=(V,E_2)$ are both planar graphs, as they coincide with the vertex-edge scheme of an icosahedron. To see that, you can think of $N,S$ as the north and south vertices, while $A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$ are the two sets of vertices with same latitude, except that in $G_1$, the set $A$ is in the north emisphere and $B$ is in the southern emisphere, and in $G_2$ it’s the opposite (and the arrangements of the points in $A$ and $B$ along the two circles of latitude is different in the two graphs).

So, since $G_1$ and $G_2$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $12$ vertices on it, and connect them with $30$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $30$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.


Example for $v=12$

An example of such a graph with thickness $2$ with $|V|=12$ is the following.

$$ V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\}, $$ $$ E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,i’)|1\leq i\leq 5\}. $$ We note that $|E|={12\choose 2}-6=60=6|V|-12$, which is the theoretical upper bound for thickness $2$ graphs. We can decompose $E$ into $$ E=E_1\cup E_2, $$ $$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=1\text{ or }2\mod 5\}, $$ $$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }3\mod 5\}. $$ Then, $G_1=(V,E_1),G_2=(V,E_2)$ are both planar graphs, as they coincide with the vertex-edge scheme of an icosahedron. To see that, you can think of $N,S$ as the north and south vertices, while $A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$ are the two sets of vertices with same latitude, except that in $G_1$, the set $A$ is in the north emisphere and $B$ is in the southern emisphere, and in $G_2$ it’s the opposite (and the arrangements of the points in $A$ and $B$ along the two circles of latitude is different).

So, since $G_1$ and $G_2$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $12$ vertices on it, and connect them with $30$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $30$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.


Example for $v=12$

An example of such a graph with thickness $2$ with $|V|=12$ is the following.

$$ V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\}, $$ $$ E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,j’)|1\leq i,j\leq 5, j-i= 3\mod 5\}. $$ We note that $|E|={12\choose 2}-6=60=6|V|-12$, which is the theoretical upper bound for thickness $2$ graphs. We can decompose $E$ into $$ E=E_1\cup E_2, $$ $$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }1\mod 5\}, $$ $$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=2\text{ or }4\mod 5\}. $$ Then, $G_1=(V,E_1),G_2=(V,E_2)$ are both planar graphs, as they coincide with the vertex-edge scheme of an icosahedron. To see that, you can think of $N,S$ as the north and south vertices, while $A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$ are the two sets of vertices with same latitude, except that in $G_1$, the set $A$ is in the north emisphere and $B$ is in the southern emisphere, and in $G_2$ it’s the opposite (and the arrangements of the points in $A$ and $B$ along the two circles of latitude is different in the two graphs).

So, since $G_1$ and $G_2$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $12$ vertices on it, and connect them with $30$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $30$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

added 194 characters in body
Source Link

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.


Example for $v=12$

An example of such a graph with thickness $2$ with $|V|=12$ is the following.

$$ V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\}, $$ $$ E=\{(N,i), (N,i’),(S,i),(S,i’),(i,j’)\,|\, 1\leq i,j\leq 5, \,i\neq j\}. $$$$ E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,i’)|1\leq i\leq 5\}. $$ We note that $|E|=60=6|V|-12$$|E|={12\choose 2}-6=60=6|V|-12$, which is the theoretical upper bound for thickness $2$ graphs. We can decompose $E$ into $$ E=E_1\cup E_2, $$ $$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=1\text{ or }2\mod 5\}, $$$$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=1\text{ or }2\mod 5\}, $$ $$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=3\text{ or }4\mod 5\}. $$$$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }3\mod 5\}. $$ Then, $G_1=(V,E_1),G_2=(V,E_2)$ are both planar graphs, as they councidecoincide with the vertex-edge scheme of an icosahedron. To see that, you can think of $N,S$ as the north and south vertices, while $A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$ are the two sets of vertices with same latitude, except that in $G_1$, the set $A$ is in the north emisphere and $B$ is in the southern emisphere, and in $G_2$ it’s the opposite (and the arrangements of the points in $A$ and $B$ along the two circles of latitude is different).

So, since $G_1$ and $G_2$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $12$ vertices on it, and connect them with $30$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $30$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.


Example for $v=12$

An example of such a graph with thickness $2$ with $|V|=12$ is the following.

$$ V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\}, $$ $$ E=\{(N,i), (N,i’),(S,i),(S,i’),(i,j’)\,|\, 1\leq i,j\leq 5, \,i\neq j\}. $$ We note that $|E|=60=6|V|-12$, which is the theoretical upper bound for thickness $2$ graphs. We can decompose $E$ into $$ E=E_1\cup E_2, $$ $$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=1\text{ or }2\mod 5\}, $$ $$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=3\text{ or }4\mod 5\}. $$ Then, $G_1=(V,E_1),G_2=(V,E_2)$ are both planar graphs, as they councide with the vertex-edge scheme of an icosahedron. To see that, you can think of $N,S$ as the north and south vertices, while $A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$ are the two sets of vertices with same latitude, except that in $G_1$, the set $A$ is in the north emisphere and $B$ is in the southern emisphere, and in $G_2$ it’s the opposite.

So, since $G_1$ and $G_2$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $12$ vertices on it, and connect them with $30$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $30$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known that to have thickness $2$, the graph must satisfy $v\geq 5$, and there is an easy upper bound to the number of edges: $$ e\leq 6v-12. $$

Note also that, if $v\geq 5$, $e=6v-12$ implies that $$ v\geq 11. $$

My question is: is the sharp upper bound on the number of edges for a graph with thickness $2$ and number of vertices $v$ known for every $v$? In particular, are there graphs $(V,E)$ with thickness two such that $e=6v-12$ for any finite set $v$ of size $v\geq 11$?

I thought about this question reading this post. Be aware though that in that post they use a different notion of thickness.


Example for $v=12$

An example of such a graph with thickness $2$ with $|V|=12$ is the following.

$$ V=\{N,1,2,3,4,5,1’,2’,3’,4’,5’,S\}, $$ $$ E=\{(v,w)\,|\,v,w\in V,v\neq w\}\setminus\{(N,S),(i,i’)|1\leq i\leq 5\}. $$ We note that $|E|={12\choose 2}-6=60=6|V|-12$, which is the theoretical upper bound for thickness $2$ graphs. We can decompose $E$ into $$ E=E_1\cup E_2, $$ $$ E_1=\{ (N,i)|1\leq i \leq 5\}\cup \{ (S,i’)|1\leq i \leq 5\}\cup\{(i,j),(i’,j’),)\,|\,j-i=1\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=1\text{ or }2\mod 5\}, $$ $$ E_2=\{ (N,i’)|1\leq i \leq 5\}\cup \{ (S,i)|1\leq i \leq 5\} \cup\{(i,j),(i’,j’),)\,|\,j-i=2\mod 5\}\cup \{ (i,j’)\,|\,1\leq i,j \leq 5,\,j-i=0\text{ or }3\mod 5\}. $$ Then, $G_1=(V,E_1),G_2=(V,E_2)$ are both planar graphs, as they coincide with the vertex-edge scheme of an icosahedron. To see that, you can think of $N,S$ as the north and south vertices, while $A:=\{1,2,3,4,5\},B:=\{1’,2’,3’,4’,5’\}$ are the two sets of vertices with same latitude, except that in $G_1$, the set $A$ is in the north emisphere and $B$ is in the southern emisphere, and in $G_2$ it’s the opposite (and the arrangements of the points in $A$ and $B$ along the two circles of latitude is different).

So, since $G_1$ and $G_2$ are planar, the graph has clearly thickness two.

The basic idea is: take a ball, draw $12$ vertices on it, and connect them with $30$ red edges to form an icosahedron (so that red edges do not intersect). Then, if you are careful enough, you can draw another $30$ blue edges, so that all edges (red and blue) connect different pairs of points, and such that blue edges do not cross each other.

Rollback to Revision 1
Source Link
Loading
The example I showed before was wrong
Source Link
Loading
Source Link
Loading