Topological graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs (connected pieces of Jordan curves) joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph.

It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other (without crossing). A topological graph is also called a drawing of a graph. An important special class of topological graphs is the class of geometric graphs, where the edges are represented by line segments.

(The term geometric graph is sometimes used in a broader, somewhat vague sense.) The theory of topological graphs is an area of graph theory, mainly concerned with combinatorial properties of topological graphs, in particular, with the crossing patterns of their edges. It is closely related to graph drawing, a field which is more application oriented, and topological graph theory, which focuses on embeddings of graphs in surfaces (that is, drawings without crossings).

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs (connected pieces of Jordan curves) joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph.

It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other (without crossing). A topological graph is also called a drawing of a graph. An important special class of topological graphs is the class of geometric graphs, where the edges are represented by line segments.

(The term geometric graph is sometimes used in a broader, somewhat vague sense.) The theory of topological graphs is an area of graph theory, mainly concerned with combinatorial properties of topological graphs, in particular, with the crossing patterns of their edges. It is closely related to graph drawing, a field which is more application oriented, and topological graph theory, which focuses on embeddings of graphs in surfaces (that is, drawings without crossings). edges, where c(k) is a constant depending only on k.

This conjecture is known to be true for k = 3 and k = 4. It is also known to be true for convex geometric graphs (that is for geometric graphs whose vertices form the vertex set of a convex n-gon), and for k-quasi-planar topological graphs whose edges are drawn as x-monotone curves, all of which cross a vertical line. The last result implies that every k-quasi-planar topological graph with n vertices, whose edges are drawn as x-monotone curves has at most c(k)n log n edges for a suitable constant c(k).

For geometric graphs, this was proved earlier by Valtr. The best known general upper bound for the number of edges of a k-quasi-planar topological graph is n\log^{O(\log k)}n . This implies that every complete topological graph with n vertices has at least n^{\frac{1}{O(\log \log n)}} pairwise crossing edges, which was improved to a quasi linear bound in the case of geometric graph. that odd-cr(G) = 0 implies cr(G) = 0. It is also known that odd-cr(G) = k implies cr(G)=k for k = 1, 2, 3. Another well researched graph parameter is the following.

Rectilinear crossing number: The minimum number of crossing points over all straight-line drawings of G in the plane (that is, all of its representations as a geometric graph) with the property that no three edges pass through the same point. It is denoted by lin-cr(G). By definition, one has cr(G) ≤ lin-cr(G) for every graph G. It was shown by Bienstock and Dean that there are graphs with crossing number 4 and with arbitrarily large rectilinear crossing number. Computing the crossing number is NP-complete in general.

Therefore a large body of research focuses on its estimates. The Crossing Lemma is a cornerstone result that provides widely applicable lower bounds on the crossing number. Several interesting variants and generalizations of the Crossing Lemma are known for Jordan curves and degenerate crossing number, where the latter relates the notion of the crossing number to the graph genus. \delta =\delta (k,d) . This result follows from the colored Tverberg theorem. It is far from the conjectured bound of O(n^{d}) .

For any fixed k > 1, we can select at most O(n^{\lceil \frac{d}{2} \rceil}) d-dimensional simplices spanned by a set of n points in \mathbb{R}^d with the property that no k of them share a common interior point. This is asymptotically tight. Two triangles in \mathbb{R}^3 are said to be almost disjoint if they are disjoint or if they share only one vertex. It is an old problem of Gil Kalai and others to decide whether the largest number of almost disjoint triangles that can be chosen on some vertex set of n points in \mathbb{R}^3 is o(n^2) .

It is known that there exists sets of n points for which this number is at least cn^{\frac 32} for a suitable constant c > 0.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368610666 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001368610666 · captured 1786321260.0 · version history

Cite this page as: encyclopegia.org, “Topological graph”, snapshot enwiki-001368610666. https://encyclopegia.org/a/topological-graph

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.