Convex partitions with 2‐edge connected dual graphs

Convex partitions with 2‐edge connected dual graphs

0.00 Avg rating0 Votes
Article ID: iaor20119244
Volume: 22
Issue: 3
Start Page Number: 409
End Page Number: 425
Publication Date: Oct 2011
Journal: Journal of Combinatorial Optimization
Authors: , , , ,
Keywords: graph partitioning, minimum spanning tree
Abstract:

It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be partitioned into open convex cells whose dual graph (defined below) is 2‐edge connected. Intuitively, every edge of the dual graph corresponds to a pair of adjacent cells that are both incident to the same vertex. Aichholzer et al. recently conjectured that given an even number of line‐segment obstacles, one can construct a convex partition by successively extending the segments along their supporting lines such that the dual graph is the union of two edge‐disjoint spanning trees. Here we present counterexamples to this conjecture, with n disjoint line segments for any n≥15, such that the dual graph of any convex partition constructed by this method has a bridge edge, and thus the dual graph cannot be partitioned into two spanning trees.

Reviews

Required fields are marked *. Your email address will not be published.