Drawing Graphs with Vertices and Edges in Convex Position

Abstract

A graph has strong convex dimension 2, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are also in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension 2 are planar and therefore have at most $3n-6$ edges. We prove that all such graphs have at most $2n-3$ edges while on the other hand we present a class of non-planar graphs of strong convex dimension 2. We also give lower bounds on the maximum number of edges a graph of strong convex dimension 2 can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years.

I. García-Marco—Supported by ANR project CompA (project number: ANR-13-BS02-0001-01)

K. Knauer—Supported by ANR EGOS grant ANR-12-JS02-002-01 and PEPS grant EROS.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A point set $X\subseteq \mathbb {R}^2$ is in (strictly) convex position if all its points are vertices of their convex hull. A point set X is said to be in weakly convex position if X lies on the boundary of its convex hull. A drawing of a graph G is an injective mapping $f:V(G)\rightarrow \mathbb {R}^2$ such that edges are straight line segments connecting vertices and neither midpoints of edges, nor vertices, nor midpoints and vertices coincide. Through most of the paper we will not distinguish between (the elements of) a graph and their drawings.

For $i,j\in \{s,w,a\}$ we define $\mathcal {G}_i^j$ as the class of graphs admitting a drawing such that the vertices are in ${\left\{ \begin{array}{ll} \text{ strictly } \text{ convex } &{}\text{ if } i=s \\ \text{ weakly } \text{ convex } &{} \text{ if } i=w \\ \text{ arbitrary } &{} \text{ if } i=a \end{array}\right. }$ position and the midpoints of edges are in ${\left\{ \begin{array}{ll} \text{ strictly } \text{ convex } &{}\text{ if } j=s \\ \text{ weakly } \text{ convex } &{} \text{ if } j=w \\ \text{ arbitrary } &{} \text{ if } j=a \end{array}\right. }$ position. Further, we define $g_i^j(n)$ to be the maximum number of edges an n-vertex graph in $\mathcal {G}_i^j$ can have.

Clearly, all $\mathcal {G}_i^j$ are closed under taking subgraphs and $\mathcal {G}_s^a=\mathcal {G}_w^a=\mathcal {G}_a^a$ is the class of all graphs.

Previous Results and Related Problems: Motivated by a special class of convex optimization problems [4], Halman, Onn, and Rothblum [3] studied drawings of graphs in $\mathbb {R}^d$ with similar constraints as described above. In particular, in their language a graph has convex dimension 2 if and only if it is in $\mathcal {G}_a^s$ and strong convex dimension 2 if and only if it is in $\mathcal {G}_s^s$. They show that all trees and cycles are in $\mathcal {G}_s^s$, while $K_4\in \mathcal {G}_a^s\setminus \mathcal {G}_s^s$ and $K_{2,3}\notin \mathcal {G}_a^s$. Moreover, they show that $n\le g_s^s(n)\le 5n-8$. Finally, they conjecture that all graphs in $\mathcal {G}_s^s$ are planar and thus $g_s^s(n)\le 3n-6$.

The problem of computing $g_a^s(n)$ and $g_s^s(n)$ was rephrased and generalized in the setting of convexly independent subsets of Minkowski sums of planar point sets by Eisenbrand et al. [2] and then regarded as a problem of computational geometry in its own right. We introduce this setting and give an overview of known results before explaining its relation to the original graph drawing problem.

Given two point sets $A, B\subseteq \mathbb {R}^d$ their Minkowski sum $A+B$ is defined as $\{a+b\mid a\in A, b\in B\}$. Define M(m, n) as the largest cardinality of a convexly independent set $X \subseteq A + B$, for A and B planar point sets with $|A|=m$ and $|B|=n$. In [2] it was shown that $M(m,n)\in O(m^{2/3}n^{2/3}+m+n)$, which was complemented with an asymptotically matching lower bound by Bílka et al. [1] even under the assumption that A itself is in convex position, i.e., $M(m,n)\in \varTheta (m^{2/3}n^{2/3}+m+n)$. Notably, the lower bound works also for the case $A=B$, as shown by Swanepoel and Valtr [5]. In [6] Tiwary gives an upper bound of $O((m+n)\log (m+n))$ for the largest cardinality of a convexly independent set $X \subseteq A + B$, for A and B planar convex point sets with $|A|=m$ and $|B|=n$. Determining the asymptotics in this case remains open.

The graph drawing problem of Halman et al. is related to the largest cardinality of a convexly independent set $X \subset A + A$, for A some planar point set. In fact, from X and A one can deduce a graph $G\in \mathcal {G}_a^s$ on vertex set A, with an edge $aa'$ for all $a\ne a'$ with $a+a'\in X$. The midpoint of the edge $aa'$ then just is $\frac{1}{2}(a+a')$. Conversely, from any $G\in \mathcal {G}_a^s$ one can construct X and A as desired. The only trade-off in this translation are the pairs of the form aa, which are not taken into account by the graph-model, because they correspond to vertices. Hence, they do not play a role from the purely asymptotic point of view. Thus, the results of [1, 2, 5] yield $g_a^s(n) = \varTheta (n^{4/3})$. Conversely, the bounds for $g_s^s(n)$ obtained in [3] give that the largest cardinality of a convexly independent set $X \subseteq A + A$, for A a planar convex point set with $|A|=n$ is in $\varTheta (n)$.

Our Results: In this paper we study the set of graph classes defined in the introduction. We endow the list of properties of point sets considered in earlier works with weak convexity. We completely determine the inclusion relations on the resulting classes. We prove that $\mathcal {G}_s^s$ contains non-planar graphs, which disproves a conjecture of Halman et al. [3], and that $\mathcal {G}_s^w$ contains cubic graphs, while we believe this to be false for $\mathcal {G}_s^s$. We give new bounds for the parameters $g_i^j(n)$: we show that $g_s^w(n)=2n-3$, which is an upper bound for $g_s^s(n)$ and therefore improves the upper bound of $3n-6$ conjectured by Halman et al. [3]. Furthermore we show that $\lfloor \frac{3}{2}(n-1)\rfloor \le g_s^s(n)$.

For the relation with Minkowski sums we show that the largest cardinality of a weakly convexly independent set $X \subseteq A + A$, for A some convex planar point set of $|A|=n$ is 2n and of a strictly convex set is between $\frac{3}{2}n$ and $2n-2$.

2 Graph Drawings

Given a graph G drawn in the plane with straight line segments as edges, we denote by $P_V$ the convex hull of its vertices and by $P_E$ the convex hull of the midpoints of its edges. Clearly, $P_E$ is strictly contained in $P_V$.

2.1 Inclusions of Classes

We show that most of the classes defined in the introduction coincide and determine the exact set of inclusions among the remaining classes.

Theorem 1

We have $\mathcal {G}_s^s=\mathcal {G}_w^s\subsetneq \mathcal {G}_s^w\subsetneq \mathcal {G}_w^w=\mathcal {G}_a^w=\mathcal {G}_s^a=\mathcal {G}_w^a=\mathcal {G}_a^a$ and $\mathcal {G}_s^s\subsetneq \mathcal {G}_a^s \subsetneq \mathcal {G}_w^w$. Moreover, there is no inclusion relationship between $\mathcal {G}_a^s$ and $\mathcal {G}_s^w$. See Fig. 1 for an illustration.

Fig. 1.

Inclusions and identities among the classes $\mathcal {G}_i^j$.

Proof

Let us begin by proving that $\mathcal {G}_s^s=\mathcal {G}_w^s$, the inclusion $\mathcal {G}_s^s \subset \mathcal {G}_w^s$ is obvious. Take $G \in \mathcal G_w^s$ drawn in the required way. We observe that there exists $\delta > 0$ such that if we move every vertex a distance $< \delta$, then the midpoints of the edges are still in convex position. Thus, whenever there are vertices $z_1,\ldots ,z_k$ in the interior of the segment connecting two vertices x, y, we do the following construction. We assume without loss of generality that x is in the point (0, 0), y is in (1, 0) and that $P_V$ is entirely contained in the closed halfplane $\{(a,b)\, \vert \, b \le 0\}$. We take $s_1, s_2 \in \mathbb {R} \cup \{\pm \infty \}$ the slopes of the previous and following edge of the boundary of $P_V$. Now we consider $\epsilon :\, 0 < \epsilon < \mathrm{min}\{\delta , \vert s_1 \vert , \vert s_2 \vert \}$, we observe that the set $P' := P_V \cup \{(a,b) \, \vert \, 0 \le a \le 1$ and $0 \le b \le \epsilon a (1-a)\}$ is convex. Then, for all $i \in \{1,\ldots ,k\}$, if $z_i$ is in $(\lambda _i,0)$ with $0 < \lambda _i < 1$, we translate $z_i$ to the point $(\lambda _i, \epsilon \lambda _i (1 - \lambda _i))$. We observe that the point $z_i$ has been moved a distance $< \epsilon /4 < \delta$ and, then, the set of midpoints of the edges is still in convex position. Moreover, now $z_1,\ldots ,z_k$ are in the boundary of $P'$. Repeating this argument when necessary we get that $G \in \mathcal G_s^{s}$.

To prove the strict inclusion $\mathcal {G}_s^s\subsetneq \mathcal {G}_s^w$ we show that the graph $K_4 - e$, i.e., the graph obtained after removing an edge e from the complete graph $K_4$ belongs to $\mathcal {G}_s^w$ but not to $\mathcal {G}_s^s$. Indeed, if we take $x_0,x_1,x_2,x_3$ the 4 vertices of $K_4 - e$ and assume that $e = x_2x_3$, it suffices to draw $x_0 = (0,1)$, $x_1 = (0,0)$, $x_2 = (1,0)$ and $x_3 = (1,2)$ to get that $K_4 - e \in \mathcal G_s^w$. Let us prove that $K_4 - e \notin \mathcal G_s^s$. Take $x_0,x_1,x_2,x_3$ in convex position, by means of an affine transformation we may assume that $x_0 = (0,1)$, $x_1 = (0,0)$, $x_2 = (1,0)$ and $x_3 = (a,b),$ with $a,b > 0$ and $a + b > 1$. If $x_ix_{i+1\ \mathrm{mod}\ 4}$ is an edge for all $i \in \{0,1,2,3\}$, then clearly $P_E$ is not convex because the midpoint of $x_0x_3$ is in the convex hull of the midpoints of the other 4 edges. So, assume that $x_2 x_3$ is not an edge, so the midpoints of the edges are in positions $m_0 = (0,1/2), m_1 = (1/2, 0)$, $m_2 = (1/2, 1/2)$, $m_3 = (a/2,b/2)$, $m_4 = (a/2, (b+1)/2)$. If $m_0, m_1, m_2, m_3$ are in convex position, then we deduce that $a < 1$ or $b < 1$ but not both. However, if $a < 1$, then $m_3$ belongs to the convex hull of $\{m_0,m_1,m_2,m_4\}$, and if $b < 1$, then $m_2$ belongs to the convex hull of $\{m_0,m_1,m_3,m_4\}$. Hence, we again have that $P_E$ is not convex and we conclude that $K_4 - e \notin \mathcal {G}_s^s$.

The strict inclusion $\mathcal {G}_s^w\subsetneq \mathcal {G}_a^a$ comes as a direct consequence of Theorem 2.

Let us see that every graph belongs to $\mathcal {G}_w^w$, for this purpose it suffices to show that $K_n \in \mathcal {G}_w^w$. Indeed, drawing the vertices in the points (0, 0), and $(1,2^i)$ for $i \in \{1,\ldots ,n-1\}$ gives the result. Then, we clearly have that $\mathcal {G}_w^w=\mathcal {G}_a^w=\mathcal {G}_s^a=\mathcal {G}_w^a=\mathcal {G}_a^a$.

The strict inclusions $\mathcal {G}_s^s\subsetneq \mathcal {G}_a^s \subsetneq \mathcal {G}_w^w$ come from the facts that $g_a^s = \varTheta (n^{4/3})$ and that, $g_s^s(n) \le g_s^w(n) \le 2n-3$ by Theorem 2. This also proves that $\mathcal {G}_a^s \not \subset \mathcal {G}_{s}^w$.

To prove that $\mathcal {G}_s^w \not \subset \mathcal {G}_{a}^s$ it suffices to consider the complete bipartite graph $K_{2,3}$. Indeed, if $\{x_1,x_2,x_3\}$, $\{y_1,y_2\}$ is the vertex partition, it suffices to draw $x_1,x_2,x_3$ in (0, 0), (4, 0), (3, 2), respectively, and $y_1, y_2$ in (1, 1), (4, 1), respectively, to get that $K_{2,3} \in \mathcal {G}_s^w$. Finally, $K_{2,3} \notin \mathcal {G}_a^s$ was already shown in [3]. $\square$

2.2 Bounds on Numbers of Edges

We show that $\lfloor \frac{3}{2}(n-1)\rfloor \le g_s^s(n)\le g_s^w(n)=2n-3$.

Whenever $P_V$ is weakly convex, for every vertex x, one can order the neighbors of x according to their clockwise appearance around the border of $P_V$ starting at x. If in this order the neighbors of x are $y_1,\ldots ,y_k$, then we say that $xy_2,\ldots ,xy_{k-1}$ are the interior edges of x. Non-interior edges of x are called exterior edges of x. Clearly, any vertex has at most two exterior edges. A vertex v sees an edge e if the straight-line segment connecting v and the midpoint $m_e$ of e does not intersect the interior of $P_E$.

Lemma 1

If $G\in \mathcal {G}_s^w$, then no vertex sees its interior edges. In particular, any vertex sees at most 2 incident edges.

Proof

Assume that there exists a vertex x seeing an interior edge $xu_i$. Take $u_1, u_k$ such that $xu_1, xu_k$ are the exterior edges of x. We consider $G'$ the induced graph with vertex set $V' = \{v,u_1,u_i,u_k\}$ and denote by $E'$ its corresponding edge set. Clearly $P_{V'} \subset P_V$ and $P_{E'} \subset P_E$, so x sees $xu_i$ in $P_{E'}$. Moreover, $xu_i$ is still an interior edge of x in $G'$. Denote by $m_j$ the midpoint of the edge $vu_j$, for $j\in \{1,i,k\}$. Since x sees $xu_i$, the closed halfplane supported by the line passing through $m_1,m_k$ containing x also contains $m_i$.

However, since $P_{V'}$ is strictly convex $u_i$ and x are separated by the line passing through $u_1,u_k$. This is a contradiction because $m_j = (u_j + x)/2$. See Fig. 2. $\square$

Fig. 2.

The construction in Lemma 1

Theorem 2

If a graph $G\in \mathcal {G}_s^w$ has n vertices, then it has at most $2n-3$ edges, i.e., $g_s^w(n)\le 2n-3$.

Proof

Take $G \in \mathcal {G}_s^w$. Since the midpoints of the edges are in weakly convex position, every edge has to be seen by one of its vertices. Lemma 1 guarantees that interior edges cannot be seen. Hence, no edge can be interior to both endpoints. This proves that G has at most 2n edges.

We improve this bound by showing that at least three edges are exterior by both their endpoints, i.e., are counted twice in the above estimate. During the proof let us call such edges doubly exterior.

Since deleting leaves only decreases the ratio of vertices and edges, we can assume that G has no leaves. Clearly, we can also assume that G has at least three edges. For an edge e, we denote by $H_e^+$ and $H_e^-$ the open halfplanes supported by the line containing e. We claim that whenever an edge $e=xy$ is an interior edge of x, then $H_e^+\cup \{x\}$ and $H_e^-\cup \{x\}$ contain a doubly exterior edge. This follows by induction on the number of vertices in $H_e^+\cap P_V$. Since e is interior to x, there is an edge $f=xz$ contained in $H_e^+\cup \{x\}$ and exterior of x. If f is doubly exterior we are done. Otherwise, we set $H_f^+$ the halfplane supported by the line containing f and not containing y. We claim that $(H_f^+\cup \{z\}) \cap P_V \subset (H_e^+\cup \{x\}) \cap P_V$. Indeed, if there is a point $v \in (H_f^+\cup \{z\}) \cap P_V$ but not in $H_e^+\cup \{x\}$, then x is in the interior of the triangle with vertices $v, y, z \in P_V$, a contradiction. Thus, $(H_f^+\cup \{z\}) \cap P_V$ is contained in $(H_e^+\cup \{x\}) \cap P_V$ and has less vertices of $P_V$, in particular, it does not contain x. By induction, we can guarantee that $(H_e^+\cup \{x\}) \cap P_V$ contains a doubly exterior edge. The same works for $H_e^-\cup \{x\}$.

Applying this argument to any edge e which is not doubly exterior gives already two doubly exterior edges f, g contained in $H_e^+\cup \{x\}$ and $H_e^-\cup \{x\}$, respectively. Choose an endpoint z of f, which is not an endpoint of g. Let $h=zw$ be the other exterior edge of z. If h is doubly exterior we are done. Otherwise, none of $H_h^+\cup \{w\}$ and $H_h^-\cup \{w\}$ contains f because $z \notin H_h^+$ and $z \notin H_h^-$; moreover one of $H_h^+\cup \{w\}$ and $H_h^-\cup \{w\}$ does not contain g. Thus, there must be a third doubly exterior edge. $\square$

Definition 1

For every $n \ge 2$, we denote by $L_n$ the graph consisting of two paths $P=(u_1, \ldots ,u_{\lfloor \frac{n}{2}\rfloor })$ and $Q=(v_1, \ldots , v_{\lceil \frac{n}{2}\rceil })$ and the edges $u_1v_1$ and $u_iv_{i-1}$ and $v_ju_{j-1}$ for $1<i\le \lfloor \frac{n}{2}\rfloor$ and $1<j\le \lceil \frac{n}{2}\rceil$. We observe that $L_n$ has $2n-3$ edges.

Theorem 3

For all $n\ge 2$ we have $L_n\in \mathcal {G}_s^w$, i.e., $g_s^w(n)\ge 2n-3$.

Proof

For every $k \ge 1$ we are constructing $L_{4k+2}\in \mathcal {G}_s^w$ (the result for other values of n follows by suppressing degree 2 vertices). We take $0 < \epsilon _0 < \epsilon _1 < \cdots < \epsilon _{2k}$ and set $\delta _j := \sum _{i = j}^{2k} \epsilon _i$ for all $j \in \{1,\ldots ,2k\}$. We consider the graph G with vertices $r_i = (i, \delta _{2i}), r_i' = (i, -\delta _{2i})$ for $i \in \{0,\ldots ,k\}$ and $\ell _i = (-i, \delta _{2i-1}), \ell _i' = (-i, -\delta _{2i-1})$ for $i \in \{1,\ldots ,k\}$; and edge set

$$\{r_0 r_0'\} \cup \{r_i \ell _i, r_i \ell _i', r_i' \ell _i, r_i'\ell _i' \, \vert \, 1 \le i \le k\} \cup \{r_{i-1} \ell _i, r_{i-1} \ell _i', r_{i-1}' \ell _i, r_{i-1}'\ell _i' \, \vert \, 1 \le i \le k\}.$$

See Fig. 3 for an illustration of the final drawing. By construction, the midpoints of the edges never coincide and they lie on the vertical lines $x = 0$ and $x = -1/2$; thus they are in weakly convex position. It is straight-forward to verify that the constructed graph is $L_{4k+2}$.    $\square$

Fig. 3.

The graph $L_6$ is in $\mathcal {G}_s^w$.

Fig. 4.

The graph $B_{11}$ is in $\mathcal {G}_s^s$.

Definition 2

For every odd $n \ge 3$, we denote by $B_n$ the graph consisting of an isolated $C_3$ and $\frac{n-3}{2}$ copies of $C_4$ altogether identified along a single edge uv. We observe that $B_n$ has $\frac{3}{2}(n-1)$ edges and deleting a degree 2 vertex from $B_{n+1}$ one obtains an n-vertex graph with $\frac{3}{2}(n-1)-\frac{1}{2}$ edges.

Theorem 4

For all odd $n\ge 3$ we have $B_n\in \mathcal {G}_s^s$, i.e., $g_s^s(n)\ge \lfloor \frac{3}{2}(n-1)\rfloor$.

Proof

Let $n\ge 3$ be such that $n-3$ is divisible by 4 (if $n-3$ is not divisible by 4, then $B_n$ is an induced subgraph of $B_{n+1}$). We will first draw $B_n$ in an unfeasible way and then transform it into another one proving $B_n\in \mathcal {G}_s^s$.

See Fig. 4 for an illustration of the final drawing.

We draw the $C_3=(uvw)$ as an isosceles triangle with horizontal base uv. Let $u=(-1,0)$, $v=(1,0)$, and $w=(0,\frac{n-1}{2})$. There are $n-3$ remaining points. Draw one half of them on coordinates $p^{\ell }_i=(-1-i,i)$ for $1\le i\le \frac{n-3}{2}$ and the other half mirrored along the y-axis, i.e., $p^r_i=(1+i,i)$ for $1\le i\le \frac{n-3}{2}$.

Now we add all edges $p^{\ell }_iu$ (left edges), $p^r_iv$ (right edges), for $1\le i\le \frac{n-3}{2}$ and edges of the form $p^{\ell }_ip^r_{\frac{n-3}{2}+1-i}$ (diagonal edges) for all $1\le i\le \frac{n-3}{2}$.

We observe that the points $p^{\ell }_i$ and u lie on the line $x + y = - 1$, the points $p^{r}_i$ and v lie on the line $x - y = 1$ and all midpoints of diagonal edges have y-coordinate $\frac{n-1}{4}$. In order to bring $P_V$ and $P_E$ into strict convex position, we simultaneously decrease the y-coordinates of points $p^{\ell }_{\frac{n-3}{2} + 1 - i}, p^r_{\frac{n-3}{2} + 1 - i}$ by $2^i \epsilon$ for $i \in \{1,\ldots ,\frac{n-3}{2}\}$ for a sufficiently small value $\epsilon > 0$. It suffices to conveniently decrease the y-coordinate of w to get a drawing witnessing that $B_n\in \mathcal {G}_s^s$. $\square$

2.3 Further Members of $\mathcal {G}_s^s$ and $\mathcal {G}_s^w$

We show that there are non-planar graphs in $\mathcal {G}_s^s$ and cubic graphs in $\mathcal {G}_s^w$.

Definition 3

For all $k \ge 2$, we denote by $H_k$ the graph consisting of a 2k-gon with vertices $v_1,\ldots ,v_{2k}$ and a singly subdivided edge from $v_i$ to for all i even, i.e., there are k degree 2 vertices $u_1,\ldots ,u_k$ and edges $u_iv_{2i}$ for all $i \in \{1,\ldots ,k\}$, $u_iv_{2i+3}$ for all $i \in \{1,\ldots ,k-2\}$, $u_{k-1}v_1$ and $u_kv_3$. We observe that $H_k$ is planar if and only if k is even.

Theorem 5

For every $k \ge 2$, $H_k \in \mathcal {G}_s^s$. In particular, for every $n \ge 9$ there is a non-planar n-vertex graph in $\mathcal {G}_s^s$.

Proof

We start by drawing $C_{2k}$ as a regular 2k-gon. Take an edge $e = xy$ and denote by $x',y'$ the neighbors of x and y, respectively. For convenience consider e to be of horizontal slope with the 2k-gon below it. Our goal is to place $v_e$ a new vertex and edges $v_e x'$, $v_e y'$ preserving the convexity of vertices and midpoints of edges. We consider the upward ray r based at the midpoint $m_e$ of e and the upward ray s of points whose x-coordinate is the average between the x-coordinates of $m_e$ and $x'$. We denote by $\varDelta$ the triangle with vertices the midpoint $m_{x'x}$ of the edge $x'x$, the point x and $m_e$. Since $s \cap \varDelta$ is nonempty, we place $v_e$ such that the midpoint of $v_ex'$ is in $s \cap \varDelta$. Clearly $v_e$ is in r. Hence, the middle point of $v_ey'$ is in the corresponding triangle $\varDelta '$ and the convexity of vertices and midpoints of edges is preserved. See Fig. 5 for an illustration. Since we only have to add a vertex on alternating edges of $C_{2k}$, these choices are independent of each other. It is easy to verify that the constructed graph is $H_k$.$\square$

Fig. 5.

The construction in Theorem 5

Definition 4

For all $k \ge 3$, we denote by $P_k$ the graph consisting of a prism over a k-cycle. We observe that $P_k$ is a 3-regular graph.

Theorem 6

For every $k \ge 3$, $P_k \in \mathcal {G}_s^w$. In particular, for every even $n\ge 6$ there is a 3-regular n-vertex graph in $\mathcal {G}_s^w$.

Proof

Let $k\ge 3$. In order to draw $P_k$, place 2k vertices $v_0, \ldots , v_{2k-1}$ as the vertices of a 2k-gon in the plane, in which all inner angles are the same and at most two different side lengths occur in alternating fashion around it. (Apart from this, these lengths do not matter for the construction.) Add all inner edges of the form for all i and outer edges for i even. Clearly, the midpoints of outer edges are in strictly convex position and their convex hull is a regular k-gon. Now, consider four vertices say $v_0, \ldots , v_3$. They induce two outer edges, $v_0v_1$ and $v_2v_3$ and two inner edges $v_0v_2$ and $v_1v_3$. Now, the triangles $v_0v_1v_2$ and $v_1v_2v_3$ share the base segment $v_1v_2$. Hence, the segments $m_{v_2v_3}m_{v_1v_3}$ and $m_{v_2v_0}m_{v_1v_0}$ share the slope of $v_1v_2$. Now, since the angle between $v_1v_2$ and $v_2v_3$ equals the angle between $v_1v_2$ and $v_0v_1$ and $v_0v_1$ and $v_2v_3$ are of equal length, the segment $m_{v_2v_3}m_{v_1v_0}$ also has the same slope. Thus, all the midpoint lie on a line and all midpoints lie on the boundary of the midpoints of outer edges. See Fig. 6 for an illustration. $\square$

Fig. 6.

The construction in Theorem 6

One can show that $P_k$ is not in $\mathcal {G}_s^s$. More generally we believe that:

Conjecture 1

If $G\in \mathcal {G}_s^s$ then G is 2-degenerate.

2.4 Structural Questions

One can show that adding a leaf at the vertex $r_1$ of $L_8$ (see Definition 1) produces a graph not in $\mathcal {G}_s^w$. Under some conditions it is possible to add leafs to graphs in $\mathcal {G}_s^s$. We say that an edge is V-crossing if it intersects the interior of $P_V$.

Proposition 1

Let $G\in \mathcal {G}_s^s$ be drawn in the required way. If uv is not V-crossing, then attaching a new vertex w to v yields a graph in $\mathcal {G}_s^s$.

Proof

Let $G\in \mathcal {G}_s^s$ with at least 3 vertices and let $e=uv$ be the edge of G from the statement. For convenience consider that uv come in clockwise order on the boundary of $P_V$. Consider the supporting hyperplane of $P_E$ through the midpoint $m_e$ of e, whose side containing $P_E$ contains v. A new midpoint can go inside the triangle $\varDelta$ defined by the two supporting hyperplanes containing $m_e$ and the additional supporting hyperplane containing the clockwisely consecutive midpoint $m'$. Since $P_E$ is contained in $P_V$ a part of $\varDelta$ lies outside $P_V$. Choosing the midpoint of a new edge attached to v inside this region very close to e preserves strict convexity of vertices and midpoints. See Fig. 7 for an illustration. $\square$

Fig. 7.

The construction in Proposition 1

We wonder whether the class $\mathcal {G}_s^s$ is closed under adding leafs.

Despite the fact that $K_{2,n} \notin \mathcal G_{s}^s$, we have found in Theorem 4 a subdivision of $K_{2,n}$ which belongs to $G_s^s$. Similarly, Theorem 5 gives that a subdivision of $K_{3,3}$ is in $G_s^s$ while $K_{3,3}$ is not. We have the impression that subdividing edges facilitates drawings in $\mathcal {G}_s^s$. Even more, we believe that:

Conjecture 2

The edges of every graph can be (multiply) subdivided such that the resulting graph is in $\mathcal {G}_s^s$.

3 Minkowski Sums

We show that the largest cardinality of a weakly convexly independent set X, which is a subset of the Minkowski sum of a convex planar n-point set A with itself is 2n. If X is required to be in strict convex position then its size lies between $\frac{3}{2}n$ and $2n-2$.

As mentioned in the introduction there is a slight trade-off when translating the graph drawing problem to the Minkowski sum problem. Since earlier works have been considering only asymptotic bounds this was neglected. Here we are fighting for constants, so we want to deal with it. Recall that a point in $x\in X\subseteq A+A$ is not captured by the graph model if $x=a+a$ for some $a\in A$. Thus, the point x corresponds to a vertex in the drawing of the graph. It is now clear, that in order to capture the trade-off we define $\widetilde{g}_i^j(n)$ as the maximum of $n'+m$, where m is the number of edges of an n-vertex graph in $\mathcal {G}_i^j$ such that $n'$ of its vertices can be added to the set of midpoints, such that the resulting set is in ${\left\{ \begin{array}{ll} \text{ strictly } \text{ convex } &{}\text{ if } j=s \\ \text{ weakly } \text{ convex } &{} \text{ if } j=w \\ \text{ arbitrary } &{} \text{ if } j=a \end{array}\right. }$ position.

Lemma 2

Let $G\in \mathcal {G}_s^w$ be drawn in the required way and $v\in G$. If v can be added to the drawing of G such that v together with the midpoints of G is in weakly convex position, then every edge $vw\in G$ is seen by w.

Proof

Otherwise the midpoint of vw will be in the convex hull of v together with parts of $P_E$ to the left and to the right of vw, see Fig. 8. $\square$

Fig. 8.

The contradiction in Lemma 2

We say that an edge is good if it can be seen by both of its endpoints.

Theorem 7

For every $n\ge 3$ we have $\widetilde{g}_s^w(n)=2n$. This is, the largest cardinality of a weakly convexly independent set $X \subseteq A + A$, for A a convex planar n-point set, is 2n.

Proof

The lower bound comes from drawing $C_n$ as the vertices and edges of a convex polygon. The set of vertices and midpoints is in weakly convex position.

For the upper bound let $G\in \mathcal {G}_s^w$ with n vertices and m edges, we denote by $n_i$ the number of vertices of G that see i of its incident edges for $i\in \{0,1,2\}$. Since every edge is seen by at least one of its endpoints and every vertex sees at most 2 of its incident edges (Lemma 1), we know that $m = n_1 + 2n_2 - m_g$, where $m_g$ is the number of good edges.

Let $n'$ be the number of vertices of G that can be added to the drawing such that together with the midpoints they are in weakly convex position. Denote by $n'_i$ the number of these vertices that see i of its incident edges for $i\in \{0,1,2\}$. By Lemma 2 the edges seen by an added vertex have to be good. Thus, $m_g\ge \frac{1}{2}(n'_1+2n'_2)$. This yields

$$m+n'\le n_1+2n_2-\frac{1}{2}(n'_1+2n'_2)+n'_0+n'_1+n'_2\le n_0+\frac{3}{2}n_1+2n_2\le 2n.$$

$\square$

Theorem 8

For every $n\ge 3$ we have $\lfloor \frac{3}{2}n\rfloor \le \widetilde{g}_s^s(n)\le 2n-2$. This is, the largest cardinality of a convexly independent set $X \subseteq A + A$, for A a convex planar n-point, lies within the above bounds.

Proof

The lower bound comes from drawing $C_n$ as the vertices and edges of a convex polygon. The set formed by an independent set of vertices and all midpoints is in convex position.

Take $G\in \mathcal {G}_s^s$ with n vertices and m edges. The upper bound is very similar to Theorem 7. Indeed, following the same notations we also get that $m = n_1 + 2n_2 - m_g$. Again, the edges seen by an added vertex have to be good. Since now moreover the set of addable vertices has to be independent, we have $m_g\ge n'_1+2n'_2$. This yields

$$m+n'\le n_1+2n_2-n'_1-2n'_2+n'_0+n'_1+n'_2\le n+n_2-n'_2.$$

If $n+n_2-n'_2>2n-2$ then either $n_2 = n$ and $n_2' < 2$, or $n_2 = n-1$ and $n_2' = 0$. In both cases we get that $n' \le 1$. By Theorem 2 we have $m\le 2n-3$, then it follows that $m+n'\le 2n-2$. $\square$

4 Conclusions

We have improved the known bounds on $g_s^s(n)$, the number of edges an n-vertex graph of strong convex dimension can have. Still describing this function exactly is open. Confirming our conjecture that graphs in $\mathcal {G}_s^s$ have degeneracy 2 would not improve our bounds. Similarly, the exact largest cardinality $\widetilde{g}_s^s(n)$ of a convexly independent set $X \subseteq A + A$ for A a convex planar n-point set, remains to be determined. Curiously, in both cases we have shown that the correct answer lies between $\frac{3}{2}n$ and 2n. The more general family $\mathcal {G}_s^w$ seems to be easier to handle, in particular we have provided the exact value for both $g_s^w$ and $\widetilde{g}_s^w$.

From a more structural point of view we wonder what graph theoretical measures can ensure that a graph is in $\mathcal {G}_s^s$ or $\mathcal {G}_s^w$. The class $\mathcal {G}_s^w$ is not closed under adding leafs. We do not know if the same holds for $\mathcal {G}_s^s$. Finally, we believe that subdividing a graph often enough ensures that it can be drawn in $\mathcal {G}_s^s$.