**Reference**:- Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth, “Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs”, in
*Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007)*, Ottawa, Ontario, Canada, August 20–22, 2007, pages 13–16. **Abstract**:-
The empty space around
*n*disjoint line segments in the plane can be partitioned into*n*+ 1 convex faces by extending the segments in some order. The*dual graph*of such a partition is the plane graph whose vertices correspond to the*n*+ 1 convex faces, and every segment endpoint corresponds to an edge between the two incident faces on opposite sides of the segment. We construct, for every set of*n*disjoint line segments in the plane, a convex partition whose dual graph is 2-edge connected. **Updates**:- Unfortunately this paper is flawed. Read our erratum (which appears in CCCG 2008, page 223).
**Length**:- The paper is 4 pages.
**Availability**:- The paper is available in PostScript (459k), gzipped PostScript (186k), and PDF (146k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.