Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{SegmentOrdering_CCCG2007,
  AUTHOR        = {Nadia M. Benbernou and Erik D. Demaine and Martin L. Demaine
                   and Michael Hoffmann and Mashhood Ishaque and
                   Diane L. Souvaine and Csaba D. T\'oth},
  TITLE         = {Disjoint Segments have Convex Partitions
                   with 2-Edge Connected Dual Graphs},
  BOOKTITLE     = {Proceedings of the 19th Canadian Conference on
                   Computational Geometry (CCCG 2007)},
  bookurl       = {http://2007.cccg.ca/},
  ADDRESS       = {Ottawa, Ontario, Canada},
  MONTH         = {August 20--22},
  YEAR          = 2007,
  PAGES         = {13--16},

  length        = {4 pages},
  withstudent   = 1,
  unrefereed    = 1,
  updates       = {Unfortunately this paper is flawed.  Read
                   <A HREF="erratum.pdf">our erratum</A>
                   (which appears in CCCG 2008, page 223).},
  dblp          = {https://dblp.org/rec/conf/cccg/BenbernouDDHIST07},
  ee            = {http://cccg.ca/proceedings/2007/01a2.pdf},
}

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]