9
$\begingroup$

The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process:

  1. Draw it in the plane such that no edge contains a vertex in its interior, and such that no more than 2 edges cross at any point.
  2. Replace every crossing point of two edges by a new vertex of degree 4.

Then the resulting graph is clearly planar. While $K_{3,n}$ has constant pathwidth, some preliminary investigations suggest that regardless of the drawing you use to planarize $K_{3,n}$, you cannot guarantee that the planarized graph has constant pathwidth independent of $n$; I believe the pathwidth of the planarized graph must grow with $n$. Is this known, or implied by some existing result?

On the other hand, I have a family of graphs of constant degree and bounded pathwidth, which I can planarize without increasing the pathwidth by more than a constant. Is there a general result saying that this is always possible for graphs of bounded degree and pathwidth?

$\endgroup$
10
$\begingroup$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why.

(1) Fix a drawing of $K_{3,n}$. Without loss of generality we can assume that no two incident edges cross and that no two edges cross twice, for otherwise we can modify the drawing to eliminate these crossings without hurting the pathwidth. Every $K_{3,3}$ subgraph of $K_{3,n}$ has a crossing, there are $n-2$ ways of extending any particular crossing to a $K_{3,3}$ subgraph, and there are $\tbinom{n}{3}$ $K_{3,3}$ subgraphs. Therefore, the number of crossings is at least $n^2/6$. (Actually a tight bound approximately $n^2/4$ is known but it doesn't change the rest.)

(2) Set $S$ to be the set of all edges in $K_{3,n}$, and consider any linear arrangement of the crossings in the whole drawing. Repeat the following steps:

(2a) Consider the point of that arrangement that bisects the crossings between pairs of edges in $S$. Define an edge of $S$ to be "cut" if all of its crossing points with other edges in $S$ are in the same half of this bisection, and "uncut" otherwise.

(2b) If there are at least $\epsilon n$ cut edges of the drawing (for some suitable constant $\epsilon$), then each of them contributes an edge of the planarization that also crosses the bisection point of the linear arrangement. This shows that the linear arrangement has vertex separation number $\Omega(n)$, but since the pathwidth is just the minimum vertex separation number of a linear arrangement, the pathwidth is also $\Omega(n)$.

(2c) In the remaining case, there are very few cut edges, so most of the crossings in $S$ come from pairs of uncut edges, which must both be on the same side of the bisection. Almost half of the $S$--$S$ crossings are on each side of the bisection, and at least one of the two sides of the bisection has fewer than half of the edges in $S$. Replace $S$ by the subset of edges on that side and repeat.

(3) Each repetition of steps (2a)–(2c) approximately doubles the density of crossings / pairs of edges in $S$, because the number of crossings is halved and the number of pairs of edges is quartered. This density already starts out constant and can't exceed one. Therefore, after a constant number of repetitions, step (2b) will succeed in finding a linear number of cut edges, showing that the pathwidth is at least linear.

As for your suggestion that bounded-degree bounded-pathwidth graphs have layouts whose planarization has bounded pathwidth: this seems indeed to be true.

Find a linear ordering of the vertices of the given graph with bounded vertex separation number: that is, at each point in a left-to-right sweep of the ordering there should be finitely many vertices left of the sweep point that have neighbors to the right. Draw the graph in a left-to-right sweep of this ordering, with its edges placed on horizontal tracks, with each of the partially completed vertices having a set of $O(1)$ tracks for its remaining edges to be connected to the right. Thus, the total number of tracks is the product of the degree with the pathwidth, $O(1)$. When you reach a new vertex, you can add nearly-vertical connectors to the tracks of other vertices that should be connected to it, and shorter connections to its outgoing tracks. Here's an example, with vertex separation number three, degree three, and three tracks per vertex.

enter image description here

This layout, also, has bounded separation number, because the only crossings are on tracks so there can be at most one vertex with an incomplete neighborhood per track. So the pathwidth of the planarization is also $O(1)$, and more precisely at most proportional to the product of the degree and the original pathwidth.

$\endgroup$
  • $\begingroup$ Beautiful and very insightful answer David, thanks a lot! I was hoping a connection to "track layouts" would show up. It turns out that the graph family I have, which has degree at most 4, can actually be planarized while increasing the pathwidth by at most an additive constant. I would be surprised if one can have only an additive increase for degree-4 graphs in general. $\endgroup$ – Bart Jansen Jun 15 '16 at 7:47
  • $\begingroup$ In your initial sentence, should $K_{2,3}$ be replaced with $K_{3,n}$? ​ ​ $\endgroup$ – user6973 Jun 15 '16 at 21:01
  • $\begingroup$ Oops, yes, fixed. $\endgroup$ – David Eppstein Jun 16 '16 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.