Constrained Tri-Connected Planar Straight Line Graphs

Marwan Al-Jubeh (), Gill Barequet (), Mashhood Ishaque (), Diane L. Souvaine (), Csaba D. Tóth () and Andrew Winslow ()
Additional contact information
Marwan Al-Jubeh: Tufts University, Department of Computer Science
Gill Barequet: Tufts University, Department of Computer Science
Mashhood Ishaque: Tufts University, Department of Computer Science
Diane L. Souvaine: Tufts University, Department of Computer Science
Csaba D. Tóth: Tufts University, Department of Computer Science
Andrew Winslow: Tufts University, Department of Computer Science

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 49-70 from Springer

Abstract: Abstract It is known that for any set V of n ≥ 4 points in the plane, not in convex position, there is a 3-connected planar straight line graph G = (V, E) with at most 2n − 2 edges, and this bound is the best possible. We show that the upper bound | E | ≤ 2n continues to hold if G = (V, E) is constrained to contain a given graph G 0 = (V, E 0), which is either a 1-factor (i.e., disjoint line segments) or a 2-factor (i.e., a collection of simple polygons), but no edge in E 0 is a proper diagonal of the convex hull of V. Since there are 1- and 2-factors with n vertices for which any 3-connected augmentation has at least 2n − 2 edges, our bound is nearly tight in these cases. We also examine possible conditions under which this bound may be improved, such as when G 0 is a collection of interior-disjoint convex polygons in a triangular container.

Keywords: Convex Hull; Planar Graph; Input Graph; Simple Polygon; Interior Vertex (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-1-4614-0110-0_5

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_5

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().