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

2025/05/30 by Pfister, Maximilian
#05C10 #05C62 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2505.24490

Abstract

We study the maximum number of straight-line segments connecting n points in convex position in the plane, so that each segment intersects at most k others. This question can also be framed as the maximum number of edges of an outer k-planar graph on n vertices. We outline several approaches to tackle the problem with the best approach yielding an upper bound of (√(2)+ε)√(k)n edges (with ε → 0 for sufficiently large 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 which might be of independent interest.

Citations

• Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
• 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth
• Beyond Outerplanarity
• On Optimal 2- and 3-Planar Graphs
• Book crossing numbers of the complete graph and small local convex crossing numbers
• On the Density of non-Simple 3-Planar Graphs
• On topological graphs with at most four crossings per edge

Related

• On the maximum number of edges in planar graphs of bounded degree and matching number
• Treewidth of Outer k-Planar Graphs
• Bounding the number of odd paths in planar graphs via convex optimization
• On the size of maximum cut in planar graphs
• How many vertex locations can be arbitrarily chosen when drawing planar graphs?