| Summary: | Let <i>P</i> be a set of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> points in general position in the plane. The edge disjointness graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>(</mo><mi>P</mi><mo>)</mo></mrow></semantics></math></inline-formula> of <i>P</i> is the graph whose vertices are the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfenced separators="" open="(" close=")"><mfrac linethickness="0pt"><mi>n</mi><mn>2</mn></mfrac></mfenced></semantics></math></inline-formula> closed straight line segments with endpoints in <i>P</i>, two of which are adjacent in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>(</mo><mi>P</mi><mo>)</mo></mrow></semantics></math></inline-formula> if and only if they are disjoint. In this paper we show that the connectivity of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>(</mo><mi>P</mi><mo>)</mo></mrow></semantics></math></inline-formula> is at most <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mfrac><mrow><mn>7</mn><msup><mi>n</mi><mn>2</mn></msup></mrow><mn>18</mn></mfrac><mo>+</mo><mo>Θ</mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, and that this upper bound is asymptotically tight. The proof is based on the analysis of the connectivity of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>(</mo><msub><mi>Q</mi><mi>n</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>Q</mi><mi>n</mi></msub></semantics></math></inline-formula> denotes an <i>n</i>-point set that is almost 3-symmetric.
|
|---|