1
$\begingroup$

Is there any analytical result or algorithm on computing the thickness of a non-complete bipartite graph?

I really tried to find anything but didn't succeed.

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is NP-hard for general graphs. Also, if you have an arbitrary graph $G$, if you subdivide each edge, you get a bipartite graph $H$ with the same thickness.

Proof. Any decomposition of $G$ into planar subgraphs corresponds to a decomposition of $H$ in which both halves of every subdivided edge are in the same planar subgraph. Call such a decomposition of $H$ "canonical". Every canonical decomposition of $H$ corresponds to a decomposition of $G$. Meanwhile, if you have a non-canonical decomposition of $H$, you can take any subdivided edge whose halves are in different planar subgraph, and move one half to join the other: this does not destroy planarity. We get a canonical decomposition with the same number of parts. So the only decompositions worth considering are canonical, and since those correspond to decompositions of $G$, the thickness of $H$ is the same as the the thickness of $G$.

Therefore the problem is NP-hard for bipartite graphs, too.

$\endgroup$
2
  • $\begingroup$ What about results on particular cases of non-complete bipartite graph and checking if it has thickness up to 2 or 3? $\endgroup$
    – Unknown
    Commented Nov 29, 2023 at 17:00
  • $\begingroup$ It is NP-complete to check if a graph has thickness 2. $\endgroup$ Commented Nov 29, 2023 at 17:51

Not the answer you're looking for? Browse other questions tagged .