On the maximum number of edges of outer k-planar graphs

Maximilian Pfister · 2025

Read On the maximum number of edges of outer k-planar graphs by Maximilian Pfister (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-2505-24490.txt.

Introduction

Maximilian Pfister bounds how many edges an outer k-planar graph can have, in his 2025 arXiv paper. Place points in convex position and join them with straight segments, allowing each segment to cross at most k others: how dense can the drawing get? His best approach gives an upper bound that grows with the square root of k times the number of points, for large k.

The paper outlines several attacks on the problem before the strongest one. A two-colored version is also studied, where segments must join opposite colors, making the graph bipartite. That detour leads through the maximum cut problem for circulant graphs, which may interest others independently.

Catalog record

CREATORMaximilian Pfister
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-24490

Browse the full library · About the Tower of Babel

Full text

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

On the maximum number of edges of outer k-planar graphs Maximilian Pfister Abstract We study the maximum number of straight-line segments connecting n n points in convex position in the plane, so that each segment intersects at most k k others. This question can also be framed as the maximum number of edges of an outer k k -planar graph on n n vertices. We outline several approaches to tackle the problem with the best approach yielding an upper bound of ( 2 + ε ) ​ k ​ n (\sqrt{2}+\varepsilon)\sqrt{k}n edges (with ε → 0 \varepsilon\rightarrow 0 for sufficiently large k k ). We further investigate the case where the points are arbitrarily bicolored and segments always connect two different colors (i.e., the corresponding graph has to be bipartite). To this end, we also consider the maximum cut problem for the circulant graph C n 1 , 2 , … , r C_{n}^{1,2,\dots,r} which might be of independent interest. Universität Tü[email protected]://orcid.org/0000-0002-7203-0669This research was supported by the DFG grant SCHL 2331/1-1 ccs Mathematics of computing Combinatorics ccs Mathematics of computing Graph Theory ccs Human-centered computing Graph Drawing keywords edge density, convex k-plane graphs, outerplanar, circulant graphs † † runningtitle: On the maximum number of edges of outer k-planar graphs † † copyright: Maximilian Pfister † † runningauthor: Maximilian Pfister 1 Introduction A geometric graph G=(P,E) is a drawing of a graph in the plane where the vertex set is drawn as a point set P in general position (that is, no three points are collinear) and each edge of E is drawn as a straight-line segment between its vertices. A geometric graph G is called (i) convex , if the pointset P is convex and (ii) plane, if no two of its edges cross (that is, share a point in their relative interior). Similarly, G is k -plane for some k\geq 0 , if each edge crosses at most k other edges. In the following, with a slight abuse of notation, we will refer to convex geometric k -plane graphs as outer k -planar graphs (since the latter family of graphs always admits a convex geometric k -plane drawing). We are concerned with the following question: Question 1 . What is the maximum number of edges an outer k -planar graph on n vertices can have? or k=0 these graphs are simply called outerplanar graphs, which have a rich history in many directions. By applying Euler’s Polyhedra Formula, one can easily derive an upper bound of 2n-3 edges for an n -vertex outerplanar graph. 1 was considered in detail for small values of k : for k=1 , [ 5 ] established a tight upper bound of \frac{5n}{2}-4 edges. For k\in\{2,3,4\} the work of [ 2 ] and [ 23 ] provided the bounds in the corresponding column of table 1 . Regarding general k , the conference version of [ 12 ] allegedly showed that outer k -planar graphs are \sqrt{4k+1}+1 degenerate - which would immediately yield an upper bound of (\sqrt{4k+1}+1)n\approx 2\sqrt{k}n edges. Unfortunately, this proof contained an error — the corrected bound [ 13 ] yields a weaker upper bound of \lfloor 3.5\sqrt{k}\rfloor n . Aichholzer et. al. [ 2 ] used the results for small values of k together with the famous Crossing Lemma tailored to the convex setting to derive an upper bound of \sqrt{\frac{243}{40}}\approx 2.465\sqrt{k}n edges, which was the previous best bound. Closely related to our problem is the problem of the maximum number of straight-line segments connecting n points in convex position, such that no k segments pairwise intersect. Graphs that admit such a drawing are called outer k -quasiplanar graphs. The maximum number of outer k -quasiplanar graphs was already settled in 1992 [ 11 ] . Recently, [ 4 ] showed that any outer k -planar graph is outer ( k+1 )-quasiplanar — as the bound of [ 11 ] is linear in k , this result is not useful regarding 1 . (a) (b) Figure 1 : (a) Illustration of the concatenation operation. (b) Illustration of the outercopy operation Our Contribution In section 3 , we consider 1 for general outer k -planar graphs. We first recall the best known lower bound construction, before we attack the upper bound from a total of four different directions, i.e., a) using known results from (non-convex) topological k -planar graphs, a) finding bounds for small values of k and applying the Crossing Lemma, a) bounding the maximum minimum degree of outer k -planar graphs and a) directly tackling the density problem. We then derive an auxiliary result in section 4 by considering the maximum cut problem for so called circulant graphs C_{n}^{1,2,\dots,r} , which will be used in section 5 where we apply our methods to bipartite outer k -planar graphs. Finally, we conclude in section 6 with open problems raised by our work and future research directions. 2 Preliminaries Throughout the paper, we will assume that G=(V,E) with |V|=n is an outer k -planar graph. With a slight abuse of notation, we will also use V to refer to the underlying pointset of G . Denote by C[G]\subset E the edges of G which are part of the convex hull of V . Any edge of E\setminus C[G] is called a diagonal of G . For a diagonal (a,b) consider the induced line L_{ab} and denote by H_{ab}^{-} ( H_{ab}^{+} ) the minimum (maximum) of the two open half-planes with respect to the number of vertices of G they contain. If H_{ab}^{-} contains t vertices, then (a,b) splits off t vertices. In this case, the length of (a,b) is t . In the following, we will define two operations on outer k -planar graphs which will be useful for the remainder of the paper. Let G_{1} and G_{2} be two outer k -planar graphs. Then G=G_{1}\mathbin{\|}G_{2} will be called the concatenation of G_{1} and G_{2} such that, V[G]=V[G_{1}]\cup V[G_{2}]\setminus\{u,v\} and E[G]=E[G_{1}]\cup E[G_{2}]-(u,v) , where (u,v) is an edge of C[G_{1}] . Informally speaking, we will identify an edge of C[G_{2}] with an edge (u,v) of C[G_{1}] and join the two graphs together, see fig. 1(a) . This procedure is also known as the clique-sum operation for a clique of size two. Let G be an outer k -plane graph. The outercopy G^{\prime}=(V^{\prime},E^{\prime}) of G with V^{\prime}=V , E^{\prime}=E[G]\cup\{e^{1}|\quad e\in E\setminus C[G]\} is obtained by copying every edge of G which does not belong to C[G] . In particular, observe that since |C[G]|\leq n , we have that |E^{\prime}|\geq 2|E|-n . Further observe that G^{\prime} is a k -planar non-homotopic (multi)-graph, i.e., there exists a drawing \Gamma^{\prime} of G^{\prime} in the plane where its vertices are mapped to points and its edges are mapped to Jordan curves such that any curve intersects at most k others - \Gamma^{\prime} is easily derived by placing the vertices of G^{\prime} on the point set V , by drawing all edges of G^{\prime} which are also contained in G as straight-line segments, while the remaining edges of G^{\prime}\setminus G^{\prime} are drawn outside of the region bounded by the convex hull of V , see fig. 1(b) . By construction, any pair of multiedges enclose some part of

Read the complete text