Convex partitions with 2-edge connected dual graphs

Marwan Al-Jubeh (), Michael Hoffmann (), Mashhood Ishaque (), Diane L. Souvaine () and Csaba D. Tóth ()
Additional contact information
Marwan Al-Jubeh: Tufts University
Michael Hoffmann: ETH Zürich
Mashhood Ishaque: Tufts University
Diane L. Souvaine: Tufts University
Csaba D. Tóth: University of Calgary

Journal of Combinatorial Optimization, 2011, vol. 22, issue 3, No 8, 409-425

Abstract: 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.

Keywords: Convex partitions; Dual graphs; Geometric matchings (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9310-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:3:d:10.1007_s10878-010-9310-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9310-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().