Squaregraph - Related Graph Classes

Related Graph Classes

The squaregraphs include as special cases trees, grid graphs, gear graphs, and the graphs of polyominos.

As well as being planar graphs, squaregraphs are median graphs, meaning that for every three vertices u, v, and w there is a unique median vertex m(u,v,w) that lies on shortest paths between each pair of the three vertices. As with median graphs more generally, squaregraphs are also partial cubes: their vertices can be labeled with binary strings such that the Hamming distance between strings is equal to the shortest path distance between vertices.

Read more about this topic:  Squaregraph

Famous quotes containing the words classes, related and/or graph:

    I am ... by tradition and long study a complete snob. P. Marlowe and I do not despise the upper classes because they take baths and have money; we despise them because they are phony.
    Raymond Chandler (1888–1959)

    Women stand related to beautiful nature around us, and the enamoured youth mixes their form with moon and stars, with woods and waters, and the pomp of summer. They heal us of awkwardness by their words and looks. We observe their intellectual influence on the most serious student. They refine and clear his mind: teach him to put a pleasing method into what is dry and difficult.
    Ralph Waldo Emerson (1803–1882)

    When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.
    Marshall McLuhan (1911–1980)