1
$\begingroup$

Take the $y$-axis and a set of $n$ curves starting from $y$-axis, labelled as $\mathcal{C}:=\{C_1,C_2,...,C_n\}$. These curves fulfill the following conditions:

  1. The curves all have a starting point somewhere on the $y$-axis and no two curves share the same starting point.

  2. At least one curve is non-$x$-monotone.

  3. Any curve intersects with any other curve at most once.

Now, I am thinking of a way to represent the set of curves $\mathcal{C}$ with a set of $x$-monotone curves, say $\mathcal{C}'=\{C_{1}',C_{2}',...,C_{n}'\}$ where the following conditions are fulfilled:

  1. All curves in $\mathcal{C}'$ have a starting point on the $y$-axis and no two curves share the same starting point.

  2. All curves in $\mathcal{C}'$ are $x$-monotone.

  3. Any curve intersects with any other curve at most once.

So I am looking for the following: would there exist a representation of $\mathcal{C}$ with $\mathcal{C}'$ in some way, or perhaps would there exist some example of $\mathcal{C}$ that is not representable by $\mathcal{C}'$? In particular, the order of the intersections of the curves do not matter, just simply the pairs of intersections in $\mathcal{C}$ and $\mathcal{C}'$ must remain the same.

Intuitively, I feel like there should exist some counter example for this, but I am struggling with coming up with such, but it also would seem difficult to prove the given statement.

It seems that maybe the proof of such could be argued with some type of a construction, for instance, labeling the curves from bottom to top as $C_1,....,C_n$ and have $C_1',...,C_n'$ correspond to these curves based on the number of intersection points on each curve. This construction seems unnecessarily complicated and I feel like there could be another way to go about this.

Also something I thought about was obtaining a general construction for this argument through something similar to a wiring diagram (see page 7 here: https://arxiv.org/pdf/1410.2350.pdf). However, I don't think this necessarily works since wiring diagrams are not necessarily $x$-monotone (although some of them can be).

$\endgroup$
3
  • $\begingroup$ What about these two curves? I think this question would be more appropriate on MSE. $\endgroup$ Commented Jul 10, 2022 at 18:01
  • 1
    $\begingroup$ Any pair of two non-monotone curves can be represented by a pair of monotone curves by the way I described. $\endgroup$ Commented Jul 10, 2022 at 18:45
  • $\begingroup$ I mean any pair of two non-monotone curves that intersect only once by the above comment ^ $\endgroup$ Commented Jul 10, 2022 at 20:08

1 Answer 1

2
$\begingroup$

This answer, as pointed out by Jan in the comment, is incorrect, as the definitions slightly differ. I leave it here as it contains useful pointers.

If I understood your definitions correctly, your $\mathcal{C}$ would be called an outerstring graph, and your $\mathcal{C}'$ a double outerstring graph. There are outerstring graphs that are not double outerstring graphs, in fact, even the order of the growth rates of these two families are different. For some literature and a nice summary of results, see the first two pages here: Alexandre Rok and Bartosz Walczak: Outerstring graphs are χ-bounded.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. If possible, could you show me an example of such a double outer string graph? Or link a paper where there is an example of such a graph? $\endgroup$ Commented Jul 10, 2022 at 23:00
  • 2
    $\begingroup$ Outerstring graphs allow more than one crossing between curves. On the other hand, double-outerstring graphs require the other endpoints on the outer face, but this is not required in the definition of $\mathcal{C}'$. Perhaps the curves in $\mathcal{C}'$ may be called grounded x-monotone: J. Pach and I. Tomon, On the chromatic number of disjointness graphs of curves (doi.org/10.1016/j.jctb.2020.02.003). But still in the paper the curves may intersect more than once. $\endgroup$
    – Jan Kyncl
    Commented Jul 11, 2022 at 3:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .