2023/12/29 by Kynčl, Jan, Soukup, Jan
#05C10 (Primary) 68R10 (Secondary) #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2312.17675
We prove the following variant of Levi's Enlargement Lemma: for an arbitrary arrangement A of x-monotone pseudosegments in the plane and a pair of points a,b with distinct x-coordinates and not on the same pseudosegment, there exists a simple x-monotone curve with endpoints a,b that intersects every curve of A at most once. As a consequence, every simple monotone drawing of a graph can be extended to a simple monotone drawing of a complete graph. We also show that extending an arrangement of cylindrically monotone pseudosegments is not always possible; in fact, the corresponding decision problem is NP-hard.