We prove the following variant of Levi’s Enlargement Lemma: for an arbitrary arrangement \(\mathcal {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 \(\mathcal {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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Extending Simple Monotone Drawings

  • Jan Kynčl,
  • Jan Soukup

摘要

We prove the following variant of Levi’s Enlargement Lemma: for an arbitrary arrangement \(\mathcal {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 \(\mathcal {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.