Untangling a Planar Graph

A straight-line drawing δ of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift(G,δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift(G,δ) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix(G,δ)=n?shift(G,δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log\log n}$ vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ _G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ _H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.     

Covering a Convex Polygon by Triangles

According to a theorem of A. V. Bogomolnaya, F. L. Nazarov and S. E. Rukshin, if n points are given inside a convex n-gon, then the points and the sides of the polygon can be numbered from 1 to n so that the triangles spanned by the ith point and the ith side(i=1....,n ) cover the polygon. In this paper, we prove that the same can be done without assuming that the given points are inside the convex n-gon. We also show that in the general case at least [(n/3)] mutually nonoverlapping triangles can be constructed in the same manner.     

Cross-Ratios and Angles Determine a Polygon

We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation. (The cross-ratio of a diagonal is the product of the ratio of edge lengths for the two adjacent triangles.) This establishes a conjecture of Driscoll and Vavasis, and shows the correctness of a key step of their algorithm for computing Schwarz—Christoffel transformations mapping a disk to a polygon. Received April 10, 1998, and in revised form March 24, 1999.     

Untangling polygons and graphs

Untangling is a process in which some vertices of a plane graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph $C_n$ while keeping at least $\mathrm{\Omega }(n^{2/3})$ vertices fixed. For any graph G, we also present an upper bound for the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound $O({(n\log n)}^{2/3})$ for all 3-vertex-connected planar graphs.     

Cylinder Multipliers Associated with a Convex Polygon

In this paper we prove that sharp weak-type estimates for the maximal operators associated with a cylindric distance function associated with a convex polygon on when 2/3 < p < 1 and , or when p = 2/3 and . This work was supported (in part) by research funds from Chosun University, 2007.     

Untangling Polygons and Graphs

Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C _n while keeping Ω(n ^2/3) vertices fixed. For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)^2/3) vertices are fixed in every untangling of δ.     

On the Area Bisectors of a Polygon

We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings of the vertices of P . We derive an algebraic characterization of area bisectors. We then show that there are simple polygons with n vertices that have Ω(n ² ) combinatorially distinct area bisectors (matching the obvious upper bound), and present an output-sensitive algorithm for computing an explicit representation of all the bisectors of a given polygon. Received September 11, 1997, and in revised form April 8, 1998.     

Exploring Polygon Rings

Some topics in mathematics are unique because they can be explored by learners from the early grades through the advanced grades. One such topic is polygon rings. As suggested in the Curriculum and Evaluation Standards for School Mathematics ( National Council of Teachers of Mathematics. 1989 ), students can learn mathematics by actively engaging in the activities outlined in this article. The activities integrate problem solving, reasoning, and communication, and they offer a fascinating look at the beauty of the structure of mathematics.     

Tiling a Polygon with Two Kinds of Rectangles

We fix two rectangles with integer dimensions. We give a quadratic time algorithm which, given a polygon F as input, produces a tiling of F with translated copies of our rectangles (or indicates that there is no tiling). Moreover, we prove that any pair of tilings can be linked by a sequence of local transformations of tilings, called flips. This study is based on the use of Conway’s tiling groups and extends the results of Kenyon and Kenyon (limited to the case when each rectangle has a side of length 1).     

The Newton Polygon of a Rational Plane Curve

The Newton polygon of the implicit equation of a rational plane curve is explicitly determined by the multiplicities of any of its parametrizations. We give an intersection-theoretical proof of this fact based on a refinement of the Kušnirenko–Bernštein theorem. We apply this result to the determination of the Newton polygon of a curve parameterized by generic Laurent polynomials or by generic rational functions, with explicit genericity conditions. We also show that the variety of rational curves with given Newton polygon is unirational and we compute its dimension. As a consequence, we obtain that any convex lattice polygon with positive area is the Newton polygon of a rational plane curve.     

Cutting a Polygon into Triangles of Equal Areas

This column is a place for those bits of contagious mathematics that travel from person to person in the community, because they are so elegant, suprising, or appealing that one has an urge to pass them on. Contributions are most welcome.     

Moving Out the Edges of a Lattice Polygon

We review previous work of (mainly) Koelman, Haase and Schicho, and Poonen and Rodriguez-Villegas on the dual operations of (i) taking the interior hull and (ii) moving out the edges of a two-dimensional lattice polygon. We show how the latter operation naturally gives rise to an algorithm for enumerating lattice polygons by their genus. We then report on an implementation of this algorithm, by means of which we produce the list of all lattice polygons (up to equivalence) whose genus is contained in {1,…,30}. In particular, we obtain the number of inequivalent lattice polygons for each of these genera. As a byproduct, we prove that the minimal possible genus for a lattice 15-gon is 45.     

Minimal Convex k-Gons Containing a Given Convex Polygon

There is a k-gon of minimal area containing a given convex n-gon (k<n) such that k-1 sides of the n-gon lie on the sides of the k-gon. All midpoints of the sides of the k-gon belong to the n-gon. Bibliography: 3 titles.     

On Distinct Distances from a Vertex of a Convex Polygon

Given a set P of n points in convex position in the plane, we prove that there exists a point such that the number of distinct distances from p is at least The best previous bound, from 1952, is due to Moser.     

Motion Planning for a Convex Polygon in a Polygonal Environment

We study the motion-planning problem for a convex m -gon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the three-dimensional space of all free placements of P in Q ) in time that is near-quadratic in mn , which is nearly optimal in the worst case. The algorithm is also conceptually simple. Previous solutions were incomplete, more expensive, or produced only part of the free configuration space. Combining our solution with parametric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also near-quadratic in mn . In addition, we describe an algorithm that preprocesses the computed free configuration space so that reachability queries can be answered in polylogarithmic time. Received September 9, 1997, and in revised form September 24, 1998.     

Polygon containment under translation

The polygon containment problem is the problem of deciding whether a polygon P can be translated to fit inside another polygon P'. We present algorithms for two cases of the polygon containment problem: when both P and P' are rectilinearly convex, and when P is convex and P' is arbitrary. In both cases the algorithms run in time O(n²logn), where n is the sum of the number of bounding edges of the two polygons. Applications to an inspection problem and a stock-cutting problem are discussed, as is the containment problem when both P and P' are nonconvex.     

Untangling two systems of noncrossing curves

We consider two systems (α₁, …, α_m) and (β₁, …,β_n) of simple curves drawn on a compact two-dimensional surface M with boundary.     

Finding the Shortest Watchman Route in a Simple Polygon

We present the first polynomial time algorithm that finds the shortest route in a simple polygon such that all points of the polygon are visible from the route. This route is called the shortest watchman route, and we do not assume any restrictions on the route or on the simple polygon. Our algorithm runs in worst case O(n ⁶ ) time, but it is adaptive, making it run faster on polygons with a simple structure. Received December 12, 1997, and in revised form September 30, 1998.     

On the Newton Polygon

Partially supported by NSF grant DMS 900-2876.