Paper by Erik D. Demaine

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.

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.

Unfortunately this paper is flawed. Read our erratum (which appears in CCCG 2008, page 223).

The paper is 4 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated May 17, 2017 by Erik Demaine.