Stabbing non-piercing sets and face lengths in large girth plane graphs

2025/04/14 by Pálvölgyi, Dömötör, Zólomy, Kristóf · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.10618

Abstract

We show that a non-piercing family of connected planar sets with bounded independence number can be stabbed with a constant number of points. As a consequence, we answer a question of Axenovich, Kießle and Sagdeev about the largest possible face length of an edge-maximal plane graph with girth at least ℓ.

Cited by

• A simple proof of a (p,2)-theorem for non-piercing regions
• Largest dyadic dual VC-dimension of non-piercing families

Related

• Stabbing Faces By a Convex Curve
• Face-hitting Dominating Sets in Planar Graphs
• On Equal Point Separation by Planar Cell Decompositions
• Faces in girth-saturated graphs on surfaces
• Constructions of point-line arrangements in the plane with large girth