Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains Ω ( n 1 2 ) pairwise disjoint edges and a plane cycle (and hence path) of length Ω ( log n log log n ) . Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.

Flip Distances Between Graph Orientations

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other? We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. More precisely, we consider so-called α -orientations of a graph G, in which every vertex v has a specified outdegree α ( v ) , and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two α -orientations of a planar graph G is at most two is NP-complete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope. It therefore provides an interesting example of a flip distance question that is computationally intractable despite having a natural interpretation as a geodesic on a nicely structured combinatorial polytope. We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard. However, if we restrict to flips that only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time. Here we exploit the fact that the flip graph is the cover graph of a distributive lattice. This generalizes a recent result from Zhang et al. (Acta Math Sin Engl Ser 35(4):569-576, 2019).

Perfect k-Colored Matchings and ( k + 2 ) -Gonal Tilings

We derive a simple bijection between geometric plane perfect matchings on 2n points in convex position and triangulations on n + 2 points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodically k-colored vertices and ( k + 2 ) -gonal tilings of convex point sets. These structures are related to a generalization of Temperley-Lieb algebras and our bijections provide explicit one-to-one relations between matchings and tilings. Moreover, for a given element of one class, the corresponding element of the other class can be computed in linear time.

Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set's chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.

Blocking Delaunay triangulations

Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of [Formula: see text] there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B: (i) [Formula: see text] white points are always sufficient to block a set of n black points, (ii) if B is in convex position, [Formula: see text] white points are always sufficient to block it, and (iii) at least [Formula: see text] white points are always necessary to block a set of n black points.

Pointed drawings of planar graphs

We study the problem how to draw a planar graph crossing-free such that every vertex is incident to an angle greater than π. In general a plane straight-line drawing cannot guarantee this property. We present algorithms which construct such drawings with either tangent-continuous biarcs or quadratic Bézier curves (parabolic arcs), even if the positions of the vertices are predefined by a given plane straight-line drawing of the graph. Moreover, the graph can be drawn with circular arcs if the vertices can be placed arbitrarily. The topic is related to non-crossing drawings of multigraphs and vertex labeling.

Matching Shapes with a Reference Point

For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in this way. The algorithm just matches the so-called Steiner points of the two sets.

The focus of our paper is the general study of reference points (like the Steiner point) and their properties with respect to shape matching.

For more general transformations than just translations, our method eliminates several degrees of freedom from the problem and thus yields good matchings with improved time bounds.