Stabbing Faces by a Convex Curve

Eppstein, David

doi:10.4230/LIPIcs.GD.2025.29

Stabbing Faces by a Convex Curve

David Eppstein Computer Science Department, University of California, Irvine, CA, USA

Abstract

We prove that, for every plane graph $G$ and every smooth convex curve $C$ not on a single line, there exists a straight-line drawing of $G$ for which every face is crossed by $C$ .

Keywords and phrases:

planar graphs, convex curves, stabbing, transversal

Funding:

David Eppstein: Research supported in part by NSF grant CCF-2212129.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Editors:

Vida Dujmović and Fabrizio Montecchiani

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

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 the full version of this paper, 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$ ,¹¹1By 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²²2By 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 the arc, as an angle.

With a stronger smoothness assumption of being twice continuously differentiable ( $C^{2}$ smoothness), the ability to cross all faces of a planar drawing would extend to non-convex smooth curves that do not lie on a line, because each such a curve has a smooth convex arc (within a neighborhood of any point of nonzero curvature) to which we can apply our proof. We omit the details.

3 Adequate drawings

We will separate out into lemmas the steps of an induction proof that a given plane graph $G$ has a drawing with all faces crossed by a given smooth convex curve $C$ . If we reinterpret the proof as a greedy construction algorithm, each step of the construction has the following property.

Figure 1: Adequate drawing of a triangulated disk (base edge shown in red) with respect to a semicircle: all boundary vertices are exterior to the semicircle and all non-base boundary edges are crossed, twice each, by disjoint arcs of the semicircle.

Definition 1.

Given an abstract triangulated disk $D$ with a specified base edge $B$ , and a smooth convex curve $C$ that is not on a single line, we define an adequate drawing of $D$ to be a straight-line drawing with the following properties:

$\blacksquare$

Every boundary vertex of $D$ is exterior to the convex hull of $C$ .
$\blacksquare$

Every boundary edge $e$ of $D$ other than $B$ is crossed twice by $C$ . The two crossing points bound an arc of $C$ that is disjoint from $D$ and from the other arcs defined in the same way from other boundary edges of $D$ .
$\blacksquare$

The crossings of $C$ with $D$ span an arc of $C$ that bends through a total curvature of less than $\pi$ .

Figure 1 depicts an example. Not all faces in this example are crossed by the convex curve $C$ (a semicircle), but the faces incident to the non-base boundary edges are crossed. As the name suggests, it will be adequate to prove that every triangulated disk formed by the canonical ordering has an adequate drawing, as every face will be adjacent to the boundary for the induced disk at some point in the ordering. This ensures the property we are really trying to prove, that the whole drawing of $G$ has every face crossed by $C$ :

Lemma 2.

Let $G$ be a maximal plane graph $G$ with $n$ vertices, with a straight-line drawing in the plane, and let $C$ be a smooth curve that is not on a single line. Suppose that $G$ has a canonical ordering with the property that, for each triangulated disk $D_{i}$ (with $3\leq i\leq n$ ) induced by the first $i$ vertices in the canonical ordering, the drawing of $G$ restricted to $D_{i}$ is adequate. Then the drawing of $G$ has all faces crossed by $C$ .

Proof.

Each face $\Delta$ of $G$ has at least one edge $e_{\Delta}$ that is a boundary edge of some $D_{i}$ , but not the base edge of the canonical ordering. For the outer face, $e_{\Delta}$ can be any non-base edge of $D_{n}$ ; for any other face, $e_{\Delta}$ is the edge of $\Delta$ induced by the first two vertices of $\Delta$ to appear in the canonical ordering. Because it is a non-base boundary edge of $D_{i}$ , and because of the assumption that the drawing of $D_{i}$ is adequate, $e_{\Delta}$ is crossed (twice) by $C$ . Near these edge crossing points, $\Delta$ itself is crossed by $C$ . $\hfill\blacktriangleleft$

4 Induction proof

We will prove our main result by induction, using canonical orderings. The next lemma is the base case for this induction proof.

Figure 2: Base case (Lemma 3): constructing an adequate drawing of a triangle by scaling an inscribed triangle with three distinct tangent slopes.

Lemma 3.

For every smooth convex curve $C$ that does not lie on a line, there exists an adequate drawing of a triangle with a designated base edge.

Proof.

Let $A$ be any arc of $C$ of nonzero curvature less than $\pi$ , and inscribe a triangle in $A$ so that the tangent lines to $A$ at its three vertices have distinct slopes; this is possible because, by smoothness and nonzero curvature, $A$ has tangents with a continuous range of slopes. Choose the base edge of this triangle to be the edge connecting the two extreme vertices in their ordering along $A$ . Scale the triangle around its centroid by a factor $1+\varepsilon$ for a parameter $\varepsilon>0$ chosen sufficiently small,

By convexity, the inscribed triangle lies in the closed convex hull of $C$ , and no point in the interior of one of its edges can lie on curve $C$ itself: if such a point existed then the convexity of $C$ would force $C$ to contain that edge, violating the assumption of distinct tangent slopes at the three vertices. Scaling brings the triangle vertices exterior to $C$ , but for sufficiently small choices of $\varepsilon$ , some points interior to each non-base edge remain interior to the convex hull of $C$ (Figure 2). Then each non-base edge of the scaled triangle will have two crossings with $C$ separating its endpoints (exterior to the hull) with the points along the edge interior to the hull. These crossings will separate disjoint arcs of $C$ , and together span an arc of $C$ that is a sub-arc of $A$ , so all the requirements of an adequate drawing are met. $\hfill\blacktriangleleft$

The simpler of the two inductive cases involves adding a single triangle as an ear of the triangulated disk, attached to it by a single boundary edge of the previous disk.

Figure 3: Ear case (Lemma 4): attaching triangle

u v w

to edge

u v

of an adequate drawing.

Lemma 4.

Let $D$ be a triangulated disk with an adequate drawing with respect to a smooth convex curve $C$ , and let $u v$ be any boundary edge of the drawing of $D$ that is not the base edge of the drawing. Then it is possible to add a vertex $w$ adjacent only to $u$ and $v$ , forming a triangle attached to $D$ across edge $u v$ , and to place $w$ in the drawing so that it becomes an an adequate drawing of the resulting augmented triangulated disk.

Proof.

For the notation used here, see Figure 3. By the assumption that the drawing of $D$ is adequate, an arc of curve $C$ crosses twice through edge $u v$ . By smoothness, this arc has a tangent line $L$ parallel to $u v$ , touching the arc at a point $x$ between the two crossings of $C$ with $u v$ . Polyline $u x v$ starts outside $C$ at $u$ , crosses inside $C$ to touch $C$ at $x$ from the interior of its convex hull, and then crosses $C$ again to reach the point $v$ exterior to $C$ . Place $w$ on a perpendicular line to $L$ through $x$ , outward from $C$ at a sufficiently small distance $\varepsilon$ from $x$ .

If $\varepsilon$ is sufficiently small, the polyline $u w v$ crosses $C$ from exterior to interior at a point near the crossing of $C$ with line segment $u x$ , and crosses again from interior to exterior at a point near the crossing of $C$ with line segment $x v$ . In order for polyline $u w v$ to be exterior to $C$ at $w$ , between these two crossings, each of the two new edges $u w$ and $w v$ must have a second crossing near $w$ . Thus, the requirements of an adequate drawing at the new boundary edges $u w$ and $w v$ are met, and the crossings of $C$ with the other boundary edges of $D$ remain unaffected, so the result is an adequate drawing. $\hfill\blacktriangleleft$

In the remaining inductive case, we add a fan of triangles, connecting an added vertex to a path of two or more edges of the triangulated disk.

Lemma 5.

Let $D$ be a triangulated disk with an adequate drawing with respect to a smooth convex curve $C$ , and let $P=v_{0}v_{1}\dots v_{k}$ be a path of $k$ boundary edges of the drawing of $D$ (for $k\geq 2$ ) that does not pass through the base edge of the drawing. Then it is possible to add a vertex $w$ adjacent to each vertex $v_{i}$ of the path, forming a fan of triangles attached to $P$ across edge $u v$ , and to place $w$ in the drawing so that it becomes an adequate drawing of the resulting augmented triangulated disk.

Proof.

For the notation used here, see Figure 4. Draw a ray from vertex $v_{0}$ through vertex $v_{1}$ , and a second ray from vertex $v_{k}$ through vertex $v_{k-1}$ . Each ray crosses $C$ at the two crossing points of an edge of $P$ . By the assumption that the drawing is adequate and therefore its crossings with $C$ span an arc of $C$ that bends through an angle less than $\pi$ , the two rays cross rather than diverging. Let $x$ be the crossing point of the two rays. At $x$ , the two crossing rays subdivide the plane into four wedges. Place $w$ interior to the wedge opposite from $P$ , at a sufficiently small distance from $w$ .

Vertices $v_{1},\dots v_{k-1}$ all lie in the wedge containing $P$ , and are visible to $x$ with respect to the given drawing of $D$ ; however, the two endpoints $v_{0}$ and $v_{k}$ of the path are blocked from visibility by $v_{1}$ and $v_{k-1}$ respectively. Placing $w$ anywhere in the wedge opposite from $P$ preserves the visibilities with $v_{1},\dots v_{k-1}$ and allows $w$ to also see the two path endpoints, producing a valid drawing of $D$ . The segments $v_{0}x$ and $xv_{k}$ cross $C$ twice, along edges $v_{0}v_{1}$ and $v_{k-1}v_{k}$ (which lie on these segments), and if $w$ is sufficiently close to $x$ then the segments $v_{0}w$ and $wv_{k}$ will also cross $C$ twice, meeting the requirements of an adequate drawing at the two new boundary edges of the augmented drawing. The crossings of $C$ with the other boundary edges of $D$ remain unaffected, so the result is an adequate drawing. $\hfill\blacktriangleleft$

Figure 4: Fan case (Lemma 5): attaching a fan of triangles to path

P=v_{0}v_{1}\dots v_{k}

of an adequate drawing.

With the lemmas above, we are ready to prove our main result:

Theorem 6.

Let $G$ be a plane graph, and let $C$ be a smooth convex curve that does not lie on a line. Then $G$ has a straight-line drawing in which all faces are crossed by $C$ .

Proof.

Augment $G$ to a maximal plane graph, and construct a canonical ordering. We prove by induction that there exists a drawing $D$ of the augmented graph such that, for each triangulated disk $D_{i}$ (with $3\leq i\leq n$ ) induced by the first $i$ vertices in the canonical ordering, the drawing restricted to $D_{i}$ is adequate. The base case $i=3$ is Lemma 3, and the induction step for each $i>4$ is either Lemma 4 (if vertex $i$ has two neighbors in $D_{i}$ ) or Lemma 5 (if vertex $i$ has three or more neighbors in $D_{i}$ . This proves that $D$ meets the hypotheses of Lemma 2, so every face of the augmented graph is crossed by $C$ . Each face of $G$ itself is a union of faces of the augmented graph, so it is also crossed by $C$ . $\hfill\blacktriangleleft$

Figure 5: Drawing of the graph of an octahedron with all faces crossed by a semicircle. The shading indicates the order in which triangles were added to the drawing in its canonical ordering, with darker triangles added earlier than lighter ones.

Our induction proof can be turned into an algorithm in which we add vertices one at a time to a drawing, using the construction of Lemma 3 to add the first three vertices, and either Lemma 4 or Lemma 5 to add each subsequent ear. An example of the resulting drawing, for the graph of an octahedron with its faces crossed by a semicircle, is shown in Figure 5. However, to analyze the numerical precision of vertex coordinates needed for this construction, and the angular resolution of the result, we would need additional assumptions about $C$ . As the figure shows, even for a well-behaved curve such as a semicircle, the angular resolution can be quite low: this construction is more useful in producing counterexamples than as a method for producing readable graph drawings.

5 Conclusions and open problems

We have shown that for every planar graph and every smooth convex curve, there exists a drawing of the graph in which all faces are crossed by the curve. The most salient remaining open problem is the one that motivated this research: is there a constant $k$ such that all planar graphs can be drawn with their vertices on $\leq k$ convex curves? It would also be of interest to more precisely characterize the graphs that can be drawn with all edges crossed by a convex curve (for which see the full version of this paper) and to extend these results to beyond-planar graphs.

References

[1] Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, and David Eppstein. Superpatterns and universal point sets. J. Graph Algorithms Appl., 18(2):177–209, 2014. Preliminary version in 21st Int. Symp. Graph Drawing, 2013, LNCS 8242, pp. 340–351. doi:10.7155/jgaa.00318.
[2] Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood. Track layouts, layered path decompositions, and leveled planarity. Algorithmica, 81(4):1561–1583, 2019. Preliminary version in 24th Int. Symp. Graph Drawing, 2016, LNCS 9801, pp. 499–510. doi:10.1007/s00453-018-0487-5.
[3] Franz J. Brandenburg. Drawing planar graphs on $\tfrac{8}{9}n^{2}$ area. In Proc. Int. Conf. Topological and Geometric Graph Theory, volume 31 of Electron. Notes Discrete Math., pages 37–40. Elsevier, 2008. doi:10.1016/j.endm.2008.06.005.
[4] Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. Drawing graphs on few lines and few planes. J. Comput. Geom., 11(1):433–475, 2020. Preliminary version in 15th Int. Symp. Algorithms and Data Structures, 2017, LNCS 10389, pp. 265–276. doi:10.20382/jocg.v11i1a17.
[5] M. Chrobak and T. H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Inform. Process. Lett., 54(4):241–246, 1995. doi:10.1016/0020-0190(95)00020-D.
[6] H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990. doi:10.1007/BF02122694.
[7] Vida Dujmović, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances Rosamond, Sue Whitesides, and David R. Wood. On the parameterized complexity of layered graph drawing. Algorithmica, 52(2):267–292, 2008. Preliminary version in 9th European Symp. Algorithms, 2001, LNCS 2161, pp. 488–499. doi:10.1007/s00453-007-9151-1.
[8] David Eppstein. Forbidden Configurations in Discrete Geometry. Cambridge University Press, 2018. Open Problem 16.14, p. 187. doi:10.1017/9781108539180.
[9] David Eppstein. Cubic planar graphs that cannot be drawn on few lines. J. Comput. Geom., 12(1):178–197, 2021. Preliminary version in 35th Int. Symp. Computational Geometry, 2019, LIPIcs 129, 32:1–32:15. doi:10.20382/v12i1a8.
[10] P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified points (solution to problem E3341). American Mathematical Monthly, 98(2):165–166, 1991. doi:10.2307/2323956.
[11] Branko Grünbaum and Hansjoachim Walther. Shortness exponents of families of graphs. J. Combinatorial Theory Ser. A, 14:364–385, 1973. doi:10.1016/0097-3165(73)90012-5.
[12] G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4–32, 1996. doi:10.1007/s004539900035.
[13] Maciej Kurowski. A 1.235 lower bound on the number of points needed to draw all $n$ -vertex planar graphs. Inform. Process. Lett., 92(2):95–98, 2004. doi:10.1016/j.ipl.2004.06.009.
[14] Alexander Ravsky and Oleg Verbitsky. On collinear sets in straight-line drawings. In Petr Kolman and Jan Kratochvíl, editors, Proc. 37th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2011), volume 6986 of Lecture Notes in Computer Science, pages 295–306. Springer, 2011. doi:10.1007/978-3-642-25870-1_27.
[15] Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner. A note on universal point sets for planar graphs. J. Graph Algorithms Appl., 24(3):247–267, 2020. Preliminary version in 27th Int. Symp. Graph Drawing, 2019, LNCS 11904, pp. 350–362. doi:10.7155/jgaa.00529.
[16] Walter Schnyder. Embedding planar graphs on the grid. In David S. Johnson, editor, Proc. 1st ACM–SIAM Symp. on Discrete Algorithms (SODA 1990), pages 138–148. SIAM, 1990. URL: https://dl.acm.org/citation.cfm?id=320176.320191.

[bib.bib1] [1] Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, and David Eppstein. Superpatterns and universal point sets. J. Graph Algorithms Appl., 18(2):177–209, 2014. Preliminary version in 21st Int. Symp. Graph Drawing, 2013, LNCS 8242, pp. 340–351. doi:10.7155/jgaa.00318.

[bib.bib2] [2] Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood. Track layouts, layered path decompositions, and leveled planarity. Algorithmica, 81(4):1561–1583, 2019. Preliminary version in 24th Int. Symp. Graph Drawing, 2016, LNCS 9801, pp. 499–510. doi:10.1007/s00453-018-0487-5.

[bib.bib3] [3] Franz J. Brandenburg. Drawing planar graphs on $\tfrac{8}{9}n^{2}$ area. In Proc. Int. Conf. Topological and Geometric Graph Theory, volume 31 of Electron. Notes Discrete Math., pages 37–40. Elsevier, 2008. doi:10.1016/j.endm.2008.06.005.

[bib.bib4] [4] Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. Drawing graphs on few lines and few planes. J. Comput. Geom., 11(1):433–475, 2020. Preliminary version in 15th Int. Symp. Algorithms and Data Structures, 2017, LNCS 10389, pp. 265–276. doi:10.20382/jocg.v11i1a17.

[bib.bib5] [5] M. Chrobak and T. H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Inform. Process. Lett., 54(4):241–246, 1995. doi:10.1016/0020-0190(95)00020-D.

[bib.bib6] [6] H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990. doi:10.1007/BF02122694.

[bib.bib7] [7] Vida Dujmović, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances Rosamond, Sue Whitesides, and David R. Wood. On the parameterized complexity of layered graph drawing. Algorithmica, 52(2):267–292, 2008. Preliminary version in 9th European Symp. Algorithms, 2001, LNCS 2161, pp. 488–499. doi:10.1007/s00453-007-9151-1.

[bib.bib8] [8] David Eppstein. Forbidden Configurations in Discrete Geometry. Cambridge University Press, 2018. Open Problem 16.14, p. 187. doi:10.1017/9781108539180.

[bib.bib9] [9] David Eppstein. Cubic planar graphs that cannot be drawn on few lines. J. Comput. Geom., 12(1):178–197, 2021. Preliminary version in 35th Int. Symp. Computational Geometry, 2019, LIPIcs 129, 32:1–32:15. doi:10.20382/v12i1a8.

[bib.bib10] [10] P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified points (solution to problem E3341). American Mathematical Monthly, 98(2):165–166, 1991. doi:10.2307/2323956.

[bib.bib11] [11] Branko Grünbaum and Hansjoachim Walther. Shortness exponents of families of graphs. J. Combinatorial Theory Ser. A, 14:364–385, 1973. doi:10.1016/0097-3165(73)90012-5.

[bib.bib12] [12] G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4–32, 1996. doi:10.1007/s004539900035.

[bib.bib13] [13] Maciej Kurowski. A 1.235 lower bound on the number of points needed to draw all $n$ -vertex planar graphs. Inform. Process. Lett., 92(2):95–98, 2004. doi:10.1016/j.ipl.2004.06.009.

[bib.bib14] [14] Alexander Ravsky and Oleg Verbitsky. On collinear sets in straight-line drawings. In Petr Kolman and Jan Kratochvíl, editors, Proc. 37th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2011), volume 6986 of Lecture Notes in Computer Science, pages 295–306. Springer, 2011. doi:10.1007/978-3-642-25870-1_27.

[bib.bib15] [15] Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner. A note on universal point sets for planar graphs. J. Graph Algorithms Appl., 24(3):247–267, 2020. Preliminary version in 27th Int. Symp. Graph Drawing, 2019, LNCS 11904, pp. 350–362. doi:10.7155/jgaa.00529.

[bib.bib16] [16] Walter Schnyder. Embedding planar graphs on the grid. In David S. Johnson, editor, Proc. 1st ACM–SIAM Symp. on Discrete Algorithms (SODA 1990), pages 138–148. SIAM, 1990. URL: https://dl.acm.org/citation.cfm?id=320176.320191.

Stabbing Faces by a Convex Curve

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries

3 Adequate drawings

Definition 1.

Lemma 2.

Proof.

4 Induction proof

Lemma 3.

Proof.

Lemma 4.

Proof.

Lemma 5.

Proof.

Theorem 6.

Proof.

5 Conclusions and open problems

References