Stabbing Faces By a Convex Curve

David Eppstein · 2025

Read Stabbing Faces By a Convex Curve by David Eppstein (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17549.txt.

Introduction

David Eppstein proves a drawing theorem for plane graphs in this 2025 mathematics paper. Take any plane graph and any smooth convex curve that is not a straight line. Eppstein shows the graph can always be drawn with straight edges so that the curve crosses every face of the drawing. No face escapes the curve: each region, including the outer one, is stabbed by it. The result joins graph drawing with a stabbing property from geometry, and the proof works for every such graph and curve at once.

Catalog record

CREATORDavid Eppstein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-17549

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stabbing Faces By a Convex Curve David Eppstein Abstract We prove that, for every plane graph G G and every smooth convex curve C C not on a single line, there exists a straight-line drawing of G G for which every face is crossed by C C . Computer Science Department, University of California, [email protected] supported in part by NSF grant CCF-2212129. {CCSXML} <ccs2012> <concept> <concept_id>10003752.10010061.10010063</concept_id> <concept_desc>Theory of computation Computational geometry</concept_desc> <concept_significance>500</concept_significance> </concept> </ccs2012> ccs Theory of computation Computational geometry keywords planar graphs, convex curves, stabbing, transversal † † runningauthor: D. Eppstein † † copyright: David Eppstein † † category: Short (Theory) 1 Introduction Every smooth convex curve C , not on a single line, contains arbitrarily many points in general position (its tangent points at distinct slopes within a suitable interval). It follows that every outerplanar graph has a straight-line drawing with all vertices on C [ 10 ] . A graph that can be drawn in this way must be outerplanar, as its vertices all belong to a common face outside C . But instead of asking for C to contain all vertices, here we ask: which planar graphs can be drawn so that C intersects all faces? The answer turns out to be all of them. Our motivation for this question comes from the problem of characterizing universal point sets, sets of points U_{n} for each n having the property that every n -vertex planar graph has a straight-line drawing with its vertices in U_{n} . These sets have size O(n^{2}) [ 6 , 16 , 3 , 1 ] , and \geq cn for a constant c>1 [ 5 , 13 , 15 ] . A recent line of research has investigated the combinatorial structure of universal point sets, in terms of the number of lines necessary to cover all points of such a set. Although point sets on O(1) parallel lines can support only the planar graphs of bounded pathwidth [ 7 ] , two crossed lines can support a much wider class of graphs, including all leveled planar graphs [ 2 ] . However, supporting all n -vertex planar graphs requires an unbounded number of lines, \Omega(n^{1/3}) [ 14 , 4 , 9 ] . Eppstein [ 8 ] asked: what if we replace lines in these results by convex curves? Is it possible that universal point sets can be supported by only O(1) convex curves? This question could be answered by finding a single planar graph G^{?} that could not be drawn with all of its faces crossed by a single convex curve. If such a graph G^{?} existed, we could assume without loss of generality that G^{?} is a triangulation, and then recursively replace triangular faces of G^{?} by more copies of G^{?} . This recursive replacement process would generate a family of graphs in which, for every drawing, every convex curve touches a number of faces bounded by a sublinear polynomial of the number of vertices. This would imply that universal point sets for graphs in this family could be supported only by a polynomially growing number of convex curves. However, the hope for a proof along these lines is dashed by our result: G^{?} does not exist. We remark that the corresponding question for edges rather than faces has an intermediate answer: the class of graphs that can be drawn with all edges touching a smooth convex curve C is broader than the outerplanar graphs but less broad than the planar graphs. In \cref sec:edges, we provide an example of a planar graph that cannot be drawn in this way, regardless of the choice of C . It takes the form of the graph of nine regular octahedra, with the outer eight octahedra each glued to a separate face of a central octahedron. But unlike the case for faces crossed by C , we do not know how to leverage this example to prove anything about the number of convex curves needed to support a universal point set. 2 Preliminaries Given a plane graph G , 1 1 1 By a plane graph we mean a planar graph together with a combinatorial embedding, which should be respected in our drawing of the graph. to be drawn with all faces crossed by a convex curve, we may assume without loss of generality that G is maximal planar, because if we complete any other graph to a maximal planar graph, and draw the result with C crossing all faces of the maximal planar completion, then C will also cross all faces of the original graph. For a maximal plane graph G , with a fixed choice of outer face, we will draw G using a canonical ordering [ 12 ] , as used by de Fraysseix, Pach, and Pollack to find grid drawings of planar graphs [ 6 ] . This is an ordering of the vertices of G such that the first three vertices in the ordering induce a triangle with one edge (the base edge ) on the outer face, and such that each prefix of the ordering induces a triangulated disk 2 2 2 By a triangulated disk , we mean a plane graph in which the outer face is a simple polygon and all interior faces are triangles. in the drawing of G , with the bounded faces of this triangulated disk also being faces of the full drawing of G . The next vertex in the ordering, after any prefix, must have as its earlier neighborhood a contiguous path along the boundary of the disk, not including the base edge, and the region between this path and the next vertex is triangulated in a fan of triangles meeting at the added vertex. This structure lends itself well to greedy incremental algorithms for planar graph drawing and to induction proofs of properties of these drawings. For every positive integer k , there exist maximal planar graphs in which, for every drawing, the number of faces of the graph that can be crossed by a line is less than a 1/k fraction of all faces [ 11 ] . These graphs therefore cannot have all faces crossed by a k -gon. To avoid these examples, our results involve smooth convex curves. There are many ways of defining curves and their smoothness; the properties we require are that the curve must form a connected subset of the boundary of a convex set in the plane (for instance, its convex hull), it must have a unique tangent line at each point, and the slope of the tangent line must be continuous along the curve ( C^{1} smoothness, meaning that the first derivative is continuous). We do not require strict convexity: our curves may contain line segments (along which the tangent slope is constant). For instance, a stadium , a convex shape obtained by attaching semicircular end caps to two opposite sides of a rectangle, has a smooth convex boundary in this sense. However, a polygon is not smooth at its vertices. An arc of a convex curve is any connected proper subset. The total curvature of an arc can be measured by the change in slopes of the tangent lines along

Read the complete text