Abstract
Given a planar straight-line graph \(G=(V,E)\) in \(\mathbb {R}^2\), a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P. We prove that every arrangement of n disjoint line segments in the plane has a subset of size \(\Omega (\sqrt{n})\) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to \(\mathbb {R}^3\). We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A more accurate term would be plane straight-line graph, but we decided to use planar straight-line graph as it is a much more commonly used term in the literature.
We thank Joe Mitchell for introducing us to the high dimensional variations of this problem.
References
Agarwal, P.K., Hurtado, F., Toussaint, G.T., Trias, J.: On polyhedra induced by point sets in space. Discrete Appl. Math. 156(1), 42–54 (2008)
Akitaya, H.A., Korman, M., Rudoy, M., Souvaine, D.L., Tóth, C.D.: Circumscribing polygons and polygonizations for disjoint line segments. In: 35th International Symposium on Computational Geometry (Portland 2019). Leibniz Int. Proc. Inform., vol. 129, # 9. Leibniz-Zent. Inform., Wadern (2019)
Barequet, G., Benbernou, N., Charlton, D., Demaine, E.D., Demaine, M.L., Ishaque, M., Lubiw, A., Schulz, A., Souvaine, D.L., Toussaint, G.T., Winslow, A.: Bounded-degree polyhedronization of point sets. Comput. Geom. 46(2), 148–153 (2013)
Cardinal, J., Hoffmann, M., Kusters, V., Tóth, C.D., Wettstein, M.: Arc diagrams, flip distances, and Hamiltonian triangulations. Comput. Geom. 68, 206–225 (2018)
Chambers, E.W., Eppstein, D., Goodrich, M.T., Löffler, M.: Drawing graphs in the plane with a prescribed outer face and polynomial area. J. Graph Algorithms Appl. 16(2), 243–259 (2012)
Chiba, N., Nishizeki, T.: The Hamiltonian cycle problem is linear-time solvable for \(4\)-connected planar graphs. J. Algorithms 10(2), 187–211 (1989)
Di Giacomo, E., Liotta, G.: The Hamiltonian augmentation problem and its applications to graph drawing. In: 4th International Workshop Algorithms and Computation (WALCOM) (Dhaka 2010). Lecture Notes in Computer Science, vol. 5942, pp. 35–46. Springer, Berlin (2010)
García, A., Noy, M., Tejel, J.: Lower bounds on the number of crossing-free subgraphs of \(K_N\). Comput. Geom. 16(4), 211–221 (2000)
Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704–714 (1976)
Grünbaum, B.: Hamiltonian polygons and polyhedra. Geombinatorics 3(3), 83–89 (1994)
Hoffmann, M., Tóth, C.D.: Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. 26(1), 47–68 (2003)
Hurtado, F., Tóth, C.D.: Plane geometric graph augmentation: a generic perspective. In: Thirty Essays on Geometric Graph Theory, pp. 327–354. Springer, New York (2013)
Ishaque, M., Souvaine, D.L., Tóth, C.D.: Disjoint compatible geometric matchings. Discrete Comput. Geom. 49(1), 89–131 (2013)
Mirzaian, A.: Hamiltonian triangulations and circumscribing polygons of disjoint line segments. Comput. Geom. 2(1), 15–30 (1992)
O’Rourke, J., Rippel, J.: Two segment classes with Hamiltonian visibility graphs. Comput. Geom. 4(4), 209–218 (1994)
Ozeki, K., Van Cleemput, N., Zamfirescu, C.T.: Hamiltonian properties of polyhedra with few 3-cuts—a survey. Discrete Math. 341(9), 2646–2660 (2018)
Pach, J., Rivera-Campo, E.: On circumscribing polygons for line segments. Comput. Geom. 10(2), 121–124 (1998)
Rappaport, D.: Computing simple circuits from a set of line segments is NP-complete. SIAM J. Comput. 18(6), 1128–1139 (1989)
Rappaport, D., Imai, H., Toussaint, G.T.: Computing simple circuits from a set of line segments. Discrete Comput. Geom. 5(3), 289–304 (1990)
Sharir, M., Sheffer, A., Welzl, E.: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique. J. Combin. Theory Ser. A 120(4), 777–794 (2013)
Tutte, W.T.: Convex representations of graphs. Proc. Lond. Math. Soc. 10, 304–320 (1960)
Urabe, M., Watanabe, M.: On a counterexample to a conjecture of Mirzaian. Comput. Geom. 2(1), 51–53 (1992)
Whitney, H.: A theorem on graphs. Ann. Math. 32(2), 378–390 (1931)
Author information
Authors and Affiliations
Additional information
Editor in Charge: János Pach
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version of this paper appeared as research supported in part by the NSF awards CCF-1422311 and CCF-1423615. Akitaya was partially supported by NSERC.
Rights and permissions
About this article
Cite this article
Akitaya, H.A., Korman, M., Korten, O. et al. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. Discrete Comput Geom 68, 218–254 (2022). https://doi.org/10.1007/s00454-021-00355-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-021-00355-8