文章基本信息

标题：Circumscribing Polygons and Polygonizations for Disjoint Line Segments
本地全文：下载
作者：Hugo A. Akitaya ; Matias Korman ; Mikhail Rudoy 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：129
页码：1-17
DOI：10.4230/LIPIcs.SoCG.2019.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given a planar straight-line graph G=(V,E) in 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 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.
关键词：circumscribing polygon; Hamiltonicity; extremal combinatorics