Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
On Alliance Partitions and Bisection Width for Planar Graphs
Vol. 17, no. 6, pp. 599-614, 2013. Regular paper.
Abstract An alliance in a graph is a set of vertices (allies) such that each vertex in the alliance has at least as many allies (counting the vertex itself) as non-allies in its neighborhood of the graph. We show how to construct infinitely many non-trivial examples of graphs that can not be partitioned into alliances and we show that any planar graph with minimum degree at least 4 can be split into two alliances in polynomial time. We base this on a proof of an upper bound of n on the bisection width for 4-connected planar graphs with an odd number of vertices. This improves a recently published n+1 upper bound on the bisection width of planar graphs without separating triangles and supports the folklore conjecture that a general upper bound of n exists for the bisection width of planar graphs.
Submitted: May 2013.
Reviewed: September 2013.
Revised: October 2013.
Accepted: October 2013.
Final: October 2013.
Published: November 2013.
Communicated by Subir Kumar Ghosh
article (PDF)