Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Squaregraph
Résumé
In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face.
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.
The graph obtained from a squaregraph by making a vertex for each zone (an equivalence class of parallel edges of quadrilaterals) and an edge for each two zones that meet in a quadrilateral is a circle graph determined by a triangle-free chord diagram of the unit disk.
Squaregraphs may be characterized in several ways other than via their planar embeddings:
They are the median graphs that do not contain as an induced subgraph any member of an infinite family of forbidden graphs. These forbidden graphs are the cube (the simplex graph of K3), the Cartesian product of an edge and a claw K1,3 (the simplex graph of a claw), and the graphs formed from a gear graph by adding one more vertex connected to the hub of the wheel (the simplex graph of the disjoint union of a cycle with an isolated vertex).
They are the graphs that are connected and bipartite, such that (if an arbitrary vertex r is picked as a root) every vertex has at most two neighbors closer to r, and such that at every vertex v, the link of v (a graph with a vertex for each edge incident to v and an edge for each 4-cycle containing v) is either a cycle of length greater than three or a disjoint union of paths.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.