William Thomas Tutte (1917-2002): British-Canadian mathematician, who made fundamental contributions to graph theory. For more, see https://uwaterloo.ca/combinatorics-and-optimization/professor-william-t-tutte.
W.T. Tutte: How to draw a graph, Proc. London Math. Soc. 13 (1963), 743-768.
N. Linial, L. Lovász & A. Wigderson: Rubber bands, convex embeddings and graph connectivity, Combinatorica, Vol. 8, 91-102, (1988)
M.X. Goemans and D.P.Williamson: .879-approximation algorithms for MAX CUT and MAX 2SAT, Proc. 26th ACM Symp. on Theory of Computing (1994), 422-431.
https://dl.acm.org/doi/10.1145/195058.195216
https://dl.acm.org/doi/10.1145/195058.195216
R.L. Brooks, C. A. B. Smith, A. H. Stone, W. T. Tutte: The dissection of rectangles into squares, Duke Math. J. 7 (1940), 312-340.
A.J.W. Duijvestijn: Simple perfect squared square of lowest order, Journal of Combinatorial Theory, Series B 25 (1978), 240-243.
A.J.W. Duijvestijn: Electronic Computation of Squared Rectangles, PhD thesis, Technische Hogeschool Eindhoven, 1962.
A graph is planar if it can be drawn in the plane so that the edges are continuous curves that do not intersect each other. Such a drawing is called an embedding of the graph in the plane.
A 3-connected planar graph, when drawn in the plane without edge crossings, divides the plane into regions called faces, which are bounded by cycles. While there are many ways to draw the graph, the family of these cycles is always the same. These cycles can be characterized by the properties that
- they have no chords, and
- deleting their nodes from the graph, it remains connected.
The dodecahedron graph is the graph formed by the vertices and edges of the dodecahedron,
one of the five platonic solids.
A graph is connected if any two of its nodes can be reached from each other on a path.
A graph is k-connected if it is connected and it stays connected if fewer than k of its nodes are deleted. (We assume that the graph has more than k nodes.)
A graph is k-connected if it is connected and it stays connected if fewer than k of its nodes are deleted. (We assume that the graph has more than k nodes.)
A graph is 3-connected if it is connected and it stays connected if any two of its nodes
are deleted. (We assume that the graph has at least four nodes.)
A cut in a graph is obtained by dividing the nodes into two classes, and taking the edges connecting nodes in different classes.
Brute force in this case means looking at all possible ways of dividing the nodes into
two classes, counting the edges that go across, and selecting the best.
Actually, in this program a useful trick called Branch-and-Bound is added: we do not look at extensions of a partial coloring if some easy calculation tells us that they are not going to beat the best cut found so far.
Actually, in this program a useful trick called Branch-and-Bound is added: we do not look at extensions of a partial coloring if some easy calculation tells us that they are not going to beat the best cut found so far.
Working out the physics: the energy of the system is defined by:
where is the position of node in the plane. Taking gradients it is easy to derive the equilibrium condition: every node that is not nailed down must be at the center of gravity of its neighbors. In formula: and
where is the position of node in the plane. Taking gradients it is easy to derive the equilibrium condition: every node that is not nailed down must be at the center of gravity of its neighbors. In formula: and