Interior (topology) | EPFL Graph Search

In mathematics, specifically in topology, the interior of a subset S of a topological space X is the union of all subsets of S that are open in X. A point that is in the interior of S is an interior point of S. The interior of S is the complement of the closure of the complement of S. In this sense interior and closure are dual notions. The exterior of a set S is the complement of the closure of S; it consists of the points that are in neither the set nor its boundary. The interior, boundary, and exterior of a subset together partition the whole space into three blocks (or fewer when one or more of these is empty). Definitions Interior point If S is a subset of a Euclidean space, then x is an interior point of S if there exists an open ball centered at x which is completely contained

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once, at endpoint or at a crossing. Let

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

. We settle Harborth's conjecture in the affirmative. 2. A \emph{monotone cylindrical} graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called \emph{simple} if any pair of its edges have at most one point in common: an endpoint or a point at which they properly cross. We say that two edges are \emph{disjoint} if they do not intersect. We show that every simple complete monotone cylindrical graph on

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

by Suk and independently by Fulek. We remark that our proof implies a polynomial time algorithm for finding this set of pairwise disjoint edges. 3. A {\em tangle} is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a {\em degenerate tangle}. We settle a problem of Pach, Radoi\v ci'c, and T'oth \cite{TTpaper}, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles. 4. We show that for a constant

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016

On Polygons Excluding Point Sets

Radoslav Fulek, Balázs Keszegh, Filip Moric

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k a parts per thousand yen K. Some other related problems are also considered.

Springer Japan2013

Degenerate crossing numbers

János Pach

Let G be a graph with n vertices and ea parts per thousand yen4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at most once, then the number of crossing points must exceed constant times (e/n)(4).

Springer-Verlag2009

Simple topological graphs

Andres Jacinto Ruiz Vargas

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016