patternModerate
Conditions for bipartite graph to be planar with no edges going around the vertices
Viewed 0 times
aroundtheedgesgraphgoingwithplanarbipartiteforconditions
Problem
A bipartite graph is planar iff it has no $K_{3, 3}$ or $K_5$ minors.
I am looking for a necessary or/and sufficient conditions to allow planar drawings with no edges "going around" sets of vertices. These are drawings satisfying:
For example, all drawings here except the bottom right are non-examples. The bottom-left graph can be re-drawn to satisfy the conditions by swapping the positions of Q and R. The tops two graphs cannot be redrawn to satisfy the conditions.
The top two graphs are the only obstructions I could find. My questions are:
Note that this is not the same as being outer-planar, $K_{2, 2}$ is outer-planar (can be drawn as a square) but it cannot be drawn to satisfy the conditions I mention above.
I am looking for a necessary or/and sufficient conditions to allow planar drawings with no edges "going around" sets of vertices. These are drawings satisfying:
- All vertices of one part are drawn on a single vertical line. Vertices of the other part are drawn on a parallel verticle line.
- Edges do not intersect except at vertices.
- Edges are all in the infinite strip between the two vertical lines in point 1.
For example, all drawings here except the bottom right are non-examples. The bottom-left graph can be re-drawn to satisfy the conditions by swapping the positions of Q and R. The tops two graphs cannot be redrawn to satisfy the conditions.
The top two graphs are the only obstructions I could find. My questions are:
- Does this problem have a name?
- Any other obstructions that I missed?
- Any hints on how I can prove that these two obstructions (along with anything I missed), as minors of course, are necessary and sufficient.
Note that this is not the same as being outer-planar, $K_{2, 2}$ is outer-planar (can be drawn as a square) but it cannot be drawn to satisfy the conditions I mention above.
Solution
Your graphs are exactly the graphs of path-width $1$ or, equivalently, the forests each of whose components is a caterpillar. Caterpillars have two relevant characterizations:
-
they're the trees in which there is a single path containing every vertex of degree more than $1$;
-
they're the trees in which every vertex has at most two non-leaf neighbours.
Lemma 1. Every caterpillar is in your class.
Proof. Let $G$ be a caterpillar and let $P=x_1\dots x_\ell$ be a longest path containing every vertex of degree $2$ or more. Note that, by maximality, $d(x_1)=d(x_\ell)=1$. We can produce a drawing of $G$ by first drawing $P$ as a zig-zag and then adding the degree-$1$ vertices adjacent to $x_i$ between $x_{i-1}$ and $x_{i+1}$. $\Box$
Lemma 2. Every graph $G$ in your class is acyclic.
Proof. Suppose $G$ contains the cycle $x_1y_1x_2y_2\dots x_ky_kx_1$ and suppose it has a drawing of the required form. W.l.o.g., $x_2$ is above $x_1$. But then we must have $y_2$ above $y_1$ since, otherwise, the lines $x_1y_1$ and $x_2y_2$ would cross. By induction, $x_{i+1}$ is above $x_i$ for all $i\in\{1, \dots, k-1\}$ and likewise for the $y$'s. But then any line $y_kx_1$ must either leave the region between the two columns of vertices or cross every other edge in the cycle. This contradicts our assumption that the graph has a proper drawing. $\Box$
Lemma 3. Every connected non-caterpillar is not in your class.
Proof. Let $G$ be a connected graph that is not a caterpillar. If it contains a cycle, it is not in your class by Lemma $2$, so we may assume it is a tree. If it is not a caterpillar, it must contain a vertex $x$ with distinct neighbours $y_1$, $y_2$ and $y_3$, each of which has degree at least $2$.
Suppose we have a drawing of $G$ with the required properties. W.l.o.g., $y_2$ is above $y_1$ and $y_3$ is above $y_2$. Let $z\neq x$ be a neighbour of $y_2$. The edge $y_2z$ must cross $xy_1$ or $xy_3$, contradicting our assumption that the graph has a drawing of the required form. $\Box$
Theorem. Your class of graphs is exactly the class of forests each of whose components is a caterpillar.
Proof. Let $G$ be a graph. Clearly, $G$ is in your class if, and only if, every component is: if any component cannot be drawn as required, the whole graph cannot; if every component can be drawn as required, then the whole graph can be drawn by arranging the components one above the other. The result now follows by Lemmas $1$ and $3$. $\Box$
Corollary. Your class of graphs is the class of graphs that do not have $K_3$ or the subdivision of $K_{1,3}$ as a minor.
Proof. These are the obstructions for path-width $1$. $\Box$
These are essentially the obstructions you found: you need $K_3$ rather than $K_4$ because the latter would admit $K_3$ into the class; the subdivision of $K_{1,3}$ is exactly your second obstruction.
-
they're the trees in which there is a single path containing every vertex of degree more than $1$;
-
they're the trees in which every vertex has at most two non-leaf neighbours.
Lemma 1. Every caterpillar is in your class.
Proof. Let $G$ be a caterpillar and let $P=x_1\dots x_\ell$ be a longest path containing every vertex of degree $2$ or more. Note that, by maximality, $d(x_1)=d(x_\ell)=1$. We can produce a drawing of $G$ by first drawing $P$ as a zig-zag and then adding the degree-$1$ vertices adjacent to $x_i$ between $x_{i-1}$ and $x_{i+1}$. $\Box$
Lemma 2. Every graph $G$ in your class is acyclic.
Proof. Suppose $G$ contains the cycle $x_1y_1x_2y_2\dots x_ky_kx_1$ and suppose it has a drawing of the required form. W.l.o.g., $x_2$ is above $x_1$. But then we must have $y_2$ above $y_1$ since, otherwise, the lines $x_1y_1$ and $x_2y_2$ would cross. By induction, $x_{i+1}$ is above $x_i$ for all $i\in\{1, \dots, k-1\}$ and likewise for the $y$'s. But then any line $y_kx_1$ must either leave the region between the two columns of vertices or cross every other edge in the cycle. This contradicts our assumption that the graph has a proper drawing. $\Box$
Lemma 3. Every connected non-caterpillar is not in your class.
Proof. Let $G$ be a connected graph that is not a caterpillar. If it contains a cycle, it is not in your class by Lemma $2$, so we may assume it is a tree. If it is not a caterpillar, it must contain a vertex $x$ with distinct neighbours $y_1$, $y_2$ and $y_3$, each of which has degree at least $2$.
Suppose we have a drawing of $G$ with the required properties. W.l.o.g., $y_2$ is above $y_1$ and $y_3$ is above $y_2$. Let $z\neq x$ be a neighbour of $y_2$. The edge $y_2z$ must cross $xy_1$ or $xy_3$, contradicting our assumption that the graph has a drawing of the required form. $\Box$
Theorem. Your class of graphs is exactly the class of forests each of whose components is a caterpillar.
Proof. Let $G$ be a graph. Clearly, $G$ is in your class if, and only if, every component is: if any component cannot be drawn as required, the whole graph cannot; if every component can be drawn as required, then the whole graph can be drawn by arranging the components one above the other. The result now follows by Lemmas $1$ and $3$. $\Box$
Corollary. Your class of graphs is the class of graphs that do not have $K_3$ or the subdivision of $K_{1,3}$ as a minor.
Proof. These are the obstructions for path-width $1$. $\Box$
These are essentially the obstructions you found: you need $K_3$ rather than $K_4$ because the latter would admit $K_3$ into the class; the subdivision of $K_{1,3}$ is exactly your second obstruction.
Context
StackExchange Computer Science Q#65088, answer score: 13
Revisions (0)
No revisions yet.