Harborth's Conjecture on:
[Wikipedia]
[Google]
[Amazon]
In 
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Harborth's conjecture states that every planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
has a planar drawing
Drawing is a Visual arts, visual art that uses an instrument to mark paper or another two-dimensional surface, or a digital representation of such. Traditionally, the instruments used to make a drawing include pencils, crayons, and ink pens, some ...
in which every edge is a straight segment of integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
length.. This conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
is named after Heiko Harborth
Heiko Harborth (born 11 February 1938, in Celle, Germany)Harborth's web site http://www.mathematik.tu-bs.de/harborth/ . Accessed 14 May 2009. is Professor of Mathematics at Braunschweig University of Technology, 1975–present, and author of mo ...
, and (if true) would strengthen Fáry's theorem
In the mathematical field of graph theory, Fáry's theorem states that any simple graph, simple, planar graph can be Graph drawing, drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as ...
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.
Special classes of graphs
Although Harborth's conjecture is not known to be true for all planar graphs, it has beenproven
Proven is a rural village in the Belgian province of West Flanders, and a "deelgemeente" of the municipality Poperinge. The village has about 1400 inhabitants.
The church and parish
A parish is a territorial entity in many Christianity, Chr ...
for several special kinds of planar graph.
One class of graphs that have integral Fáry embeddings are the graphs that can be reduced to the empty graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is t ...
by a sequence of operations of two types:
*Removing a vertex of degree at most two.
*Replacing a vertex of degree three by an edge between two of its neighbors. (If such an edge already exists, the degree three vertex can be removed without adding another edge between its neighbors.)
For such a graph, a rational
Rationality is the quality of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...
Fáry embedding can be constructed incrementally by reversing this removal process, re-inserting the vertices that were removed. Re-inserting a degree-two vertex uses the fact that the set of points that are at a rational distance from two given points are dense
Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be use ...
in the plane. Re-inserting a degree-three vertex uses the fact that, if three points have rational distance between one pair and square-root-of-rational distance between the other two pairs, then the points at rational distances from all three are again dense in the plane. The distances in such an embedding can be made into integers by scaling the embedding by an appropriate factor. Based on this construction, the graphs known to have integral Fáry embeddings include the bipartite planar graphs, (2,1)-sparse planar graphs, planar graphs of treewidth
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
...
at most 3, and graphs of degree at most four that either contain a diamond
Diamond is a Allotropes of carbon, solid form of the element carbon with its atoms arranged in a crystal structure called diamond cubic. Diamond is tasteless, odourless, strong, brittle solid, colourless in pure form, a poor conductor of e ...
subgraph or are not 4-edge-connected.
In particular, the graphs that can be reduced to the empty graph by the removal only of vertices of degree at most two (the 2-degenerate planar graphs) include both the outerplanar graph
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.
Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two f ...
s and the series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
s. However, for the outerplanar graphs a more direct construction of integral Fáry embeddings is possible, based on the existence of infinite subsets of the unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucli ...
in which all distances are rational.
Additionally, integral Fáry embeddings are known for each of the five Platonic solid
In geometry, a Platonic solid is a Convex polytope, convex, regular polyhedron in three-dimensional space, three-dimensional Euclidean space. Being a regular polyhedron means that the face (geometry), faces are congruence (geometry), congruent (id ...
s.
Related conjectures
A stronger version of Harborth's conjecture, posed by , asks whether every planar graph has a planar drawing in which the vertex coordinates as well as the edge lengths are all integers. It is known to be true for 3-regular graphs, for graphs that have maximum degree 4 but are not 4-regular,. and for planar 3-trees. Another unsolved problem ingeometry
Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
, the Erdős–Ulam problem, concerns the existence of dense subsets of the plane in which all distances are rational numbers. If such a subset existed, it would form a universal point set that could be used to draw all planar graphs with rational edge lengths (and therefore, after scaling them appropriately, with integer edge lengths). However, Ulam conjectured that dense rational-distance sets do not exist..
According to the Erdős–Anning theorem
The Erdős–Anning theorem states that, whenever an Infinite set, infinite number of points in the plane all have integer distances, the points lie on a straight line. The same result holds in higher dimensional Euclidean spaces.
The theorem ca ...
, infinite non-collinear point sets with all distances being integers cannot exist. This does not rule out the existence of sets with all distances rational, but it does imply that in any such set the denominators of the rational distances must grow arbitrarily large.
See also
*Integer triangle
An integer triangle or integral triangle is a triangle all of whose side lengths are integers. A rational triangle is one whose side lengths are rational numbers; any rational triangle can be rescaled by the lowest common denominator of the s ...
, an integral Fáry embedding of the triangle graph
In the mathematical field of graph theory, the triangle graph is a planar undirected graph with 3 vertices and 3 edges, in the form of a triangle.
The triangle graph is also known as the cycle graph C_3 and the complete graph K_3.
Properties ...
*Matchstick graph
In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an ...
, a graph that can be drawn planarly with all edge lengths equal to 1
*Erdős–Diophantine graph
An Erdős–Diophantine graph is an object in the mathematical subject of Diophantine equations consisting of a set of integer points at integer distances in the plane that cannot be extended by any additional points. Equivalently, in geometric ...
, a complete graph with integer distances that cannot be extended to a larger complete graph with the same property
*Euler brick
In mathematics, an Euler brick, named after Leonhard Euler, is a rectangular cuboid whose edges and face diagonals all have integer lengths. A primitive Euler brick is an Euler brick whose edge lengths are relatively prime. A perfect Euler brick ...
, an integer-distance realization problem in three dimensions
References
{{reflist, 30em Conjectures Unsolved problems in graph theory Statements about planar graphs Arithmetic problems of plane geometry