Universal point set

Last updated
Unsolved problem in mathematics:

Do planar graphs have universal point sets of subquadratic size?

Contents

(more unsolved problems in mathematics)

In graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.

Bounds on the size of universal point sets

Grid drawing of a nested triangles graph. In any drawing of this graph, at least half of the triangles must form a nested chain, which requires a bounding box of size at least n/3 x n/3. The layout shown here comes close to this, using size approximately n/3 x n/2 Nested triangle graph grid.svg
Grid drawing of a nested triangles graph. In any drawing of this graph, at least half of the triangles must form a nested chain, which requires a bounding box of size at least n/3 × n/3. The layout shown here comes close to this, using size approximately n/3 × n/2

When n is ten or less, there exist universal point sets with exactly n points, but for all n ≥ 15 additional points are required. [1]

Several authors have shown that subsets of the integer lattice of size O(n) × O(n) are universal. In particular, de Fraysseix, Pach & Pollack (1988) showed that a grid of (2n − 3) × (n − 1) points is universal, and Schnyder (1990) reduced this to a triangular subset of an (n − 1) × (n − 1) grid, with n2/2 − O(n) points. By modifying the method of de Fraysseix et al., Brandenburg (2008) found an embedding of any planar graph into a triangular subset of the grid consisting of 4n2/9 points. A universal point set in the form of a rectangular grid must have size at least n/3 × n/3 [2] but this does not rule out the possibility of smaller universal point sets of other types. The smallest known universal point sets are not based on grids, but are instead constructed from superpatterns (permutations that contain all permutation patterns of a given size); the universal point sets constructed in this way have size n2/4 − Θ(n). [3]

de Fraysseix, Pach & Pollack (1988) proved the first nontrivial lower bound on the size of a universal point set, with a bound of the form n + Ω(√n), and Chrobak & Karloff (1989) showed that universal point sets must contain at least 1.098n − o(n) points. Kurowski (2004) stated an even stronger bound of 1.235n − o(n), [4] which was further improved by Scheucher, Schrezenmaier & Steiner (2018) to 1.293n − o(n).

Closing the gap between the known linear lower bounds and quadratic upper bounds remains an open problem. [5]

Special classes of graphs

Subclasses of the planar graphs may, in general, have smaller universal sets (sets of points that allow straight-line drawings of all n-vertex graphs in the subclass) than the full class of planar graphs, and in many cases universal point sets of exactly n points are possible. For instance, it is not hard to see that every set of n points in convex position (forming the vertices of a convex polygon) is universal for the n-vertex outerplanar graphs, and in particular for trees. Less obviously, every set of n points in general position (no three collinear) remains universal for outerplanar graphs. [6]

Planar graphs that can be partitioned into nested cycles, 2-outerplanar graphs and planar graphs of bounded pathwidth, have universal point sets of nearly-linear size. [7] Planar 3-trees have universal point sets of size O(n3/2 log n); the same bound also applies to series–parallel graphs. [8]

Other drawing styles

An arc diagram Goldner-Harary-linear.svg
An arc diagram

As well as for straight-line graph drawing, universal point sets have been studied for other drawing styles; in many of these cases, universal point sets with exactly n points exist, based on a topological book embedding in which the vertices are placed along a line in the plane and the edges are drawn as curves that cross this line at most once. For instance, every set of n collinear points is universal for an arc diagram in which each edge is represented as either a single semicircle or a smooth curve formed from two semicircles. [9]

By using a similar layout, every strictly convex curve in the plane can be shown to contain an n-point subset that is universal for polyline drawing with at most one bend per edge. [10] This set contains only the vertices of the drawing, not the bends; larger sets are known that can be used for polyline drawing with all vertices and all bends placed within the set. [11]

Notes

  1. ↑ Cardinal, Hoffmann & Kusters (2015).
  2. ↑ Dolev, Leighton & Trickey (1984); Chrobak & Karloff (1989); Demaine & O'Rourke (2002–2012). A weaker quadratic lower bound on the grid size needed for planar graph drawing was given earlier by Valiant (1981).
  3. ↑ Bannister et al. (2013).
  4. ↑ Mondal (2012) claimed that Kurowski's proof was erroneous, but later (after discussion with Jean Cardinal) retracted this claim; see Explanation Supporting Kurowski's Proof, D. Mondal, updated August 9, 2013.
  5. ↑ Demaine & O'Rourke (2002–2012); Brandenburg et al. (2003); Mohar (2007).
  6. ↑ Gritzmann et al. (1991).
  7. ↑ Angelini et al. (2018); Bannister et al. (2013).
  8. ↑ Fulek & Tóth (2015)
  9. ↑ Giordano et al. (2007).
  10. ↑ Everett et al. (2010).
  11. ↑ Dujmović et al. (2013).

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">No-three-in-line problem</span> Geometry problem on grid points

The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".

<span class="mw-page-title-main">Scheinerman's conjecture</span> Mathematics theorem

In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane. It was proven by Jeremie Chalopin and Daniel Gonçalves (2009).

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

<span class="mw-page-title-main">Book embedding</span> Graph layout on multiple half-planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

Planarity is a puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">János Pach</span> Hungarian mathematician

János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.

<span class="mw-page-title-main">Topological graph</span>

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 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. A topological graph is also called a drawing of a graph.

<span class="mw-page-title-main">1-planar graph</span>

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

<span class="mw-page-title-main">Upward planar drawing</span> Graph with edges non-crossing and upward

In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge should have the property that every horizontal line intersects it in at most one point, and no two edges may intersect except at a shared endpoint. In this sense, it is the ideal case for layered graph drawing, a style of graph drawing in which edges are monotonic curves that may cross, but in which crossings are to be minimized.

In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.

In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.

<span class="mw-page-title-main">Harborth's conjecture</span> On graph drawing with integer edge lengths

In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which every edge is a straight segment of integer length. This conjecture is named after Heiko Harborth, and would strengthen Fáry's theorem on the existence of straight-line drawings for every planar graph. For this reason, a drawing with integer edge lengths is also known as an integral Fáry embedding. Despite much subsequent research, Harborth's conjecture remains unsolved.

<span class="mw-page-title-main">Queue number</span> Invariant in graph theory

In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.

Simultaneous embedding is a technique in graph drawing and information visualization for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between an edge of one graph and an edge of the other graph are allowed.

<span class="mw-page-title-main">Penny graph</span> Graph formed by touching unit circles

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.