  Communication
Free Faster access than browser!

Planar graph

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. 

100 relations: Algorithm, Apex graph, Apollonian network, Big O notation, Branch-decomposition, Butterfly graph, Chordal graph, Circle packing theorem, Circuit rank, Clique-sum, Colin de Verdière graph invariant, Combinatorial map, Complete bipartite graph, Complete graph, Connectivity (graph theory), Convex polygon, Convex polytope, Cycle (graph theory), Cycle space, David Bader (computer scientist), Dense graph, Directed acyclic graph, Dual graph, Equivalence class, Euler characteristic, Fáry's theorem, Forbidden graph characterization, Four color theorem, Genus (mathematics), Geometric graph theory, Glossary of graph theory terms, Graph (discrete mathematics), Graph coloring, Graph embedding, Graph isomorphism problem, Graph minor, Graph theory, Halin graph, Hanani–Tutte theorem, Homeomorphism, Homeomorphism (graph theory), If and only if, Integer lattice, Intersection graph, Isomorphism, Journal of Graph Algorithms and Applications, K-tree, K-vertex-connected graph, Kazimierz Kuratowski, Klaus Wagner, ... Expand index (50 more) »

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex.

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles.

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

Branch-decomposition

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves.

Butterfly graph

In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar undirected graph with 5 vertices and 6 edges.

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.

Circle packing theorem

The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint.

Circuit rank

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest.

Clique-sum

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology.

Colin de Verdière graph invariant

Colin de Verdière's invariant is a graph parameter \mu(G) for any graph G, introduced by Yves Colin de Verdière in 1990.

Combinatorial map

A combinatorial map is a combinatorial object modelling topological structures with subdivided objects.

No description.

No description.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.

Convex polygon

A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon.

Convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn.

Cycle (graph theory)

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

Cycle space

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its Eulerian subgraphs.

David A. Bader (born May 4, 1969) is a Professor, Chair of the School of Computational Science and Engineering, and Executive Director of High-Performance Computing in the Georgia Tech College of Computing.

Dense graph

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges.

Directed acyclic graph

In mathematics and computer science, a directed acyclic graph (DAG), is a finite directed graph with no directed cycles.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of.

Equivalence class

In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation) defined on them, then one may naturally split the set S into equivalence classes.

Euler characteristic

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler&ndash;Poincaré characteristic) is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent.

Fáry's theorem

In mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments.

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

Four color theorem

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.

Genus (mathematics)

In mathematics, genus (plural genera) has a few different, but closely related, meanings.

Geometric graph theory

A geometric graph is a graph in which the vertices or edges are associated with geometric objects, the simplest realisation is a Random geometric graph.

Glossary of graph theory terms

This is a glossary of graph theory terms.

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

Graph embedding

In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of) are associated with edges in such a way that.

Graph isomorphism problem

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

Halin graph

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.

Hanani–Tutte theorem

In topological graph theory, the Hanani–Tutte theorem is a result on the parity of edge crossings in a graph drawing.

Homeomorphism

In the mathematical field of topology, a homeomorphism or topological isomorphism or bi continuous function is a continuous function between topological spaces that has a continuous inverse function.

Homeomorphism (graph theory)

In graph theory, two graphs G and G' are homeomorphic if there is a graph isomorphism from some subdivision of G to some subdivision of G'.

If and only if

In logic and related fields such as mathematics and philosophy, if and only if (shortened iff) is a biconditional logical connective between statements.

Integer lattice

In mathematics, the n-dimensional integer lattice (or cubic lattice), denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are ''n''-tuples of integers.

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets.

Isomorphism

In mathematics, an isomorphism (from the Ancient Greek: ἴσος isos "equal", and μορφή morphe "form" or "shape") is a homomorphism or morphism (i.e. a mathematical mapping) that can be reversed by an inverse morphism.

Journal of Graph Algorithms and Applications

The Journal of Graph Algorithms and Applications is an open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing.

K-tree

In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that, together, the k + 1 vertices form a clique.

K-vertex-connected graph

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

Kazimierz Kuratowski

Kazimierz Kuratowski (Polish pronunciation:, 2 February 1896 – 18 June 1980) was a Polish mathematician and logician.

Klaus Wagner

Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician.

Kuratowski's theorem

In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski.

Left-right planarity test

In graph theory, a branch of mathematics, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion is a characterization of planar graphs based on the properties of the depth-first search trees, published by and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm.

Line (geometry)

The notion of line or straight line was introduced by ancient mathematicians to represent straight objects (i.e., having no curvature) with negligible width and depth.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.

Line segment

In geometry, a line segment is a part of a line that is bounded by two distinct end points, and contains every point on the line between its endpoints.

In mathematics, the linking number is a numerical invariant that describes the linking of two closed curves in three-dimensional space.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph are linked.

Mac Lane's planarity criterion

In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937.

Map graph

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane.

Mathematical induction

Mathematical induction is a mathematical proof technique.

Meshedness coefficient

In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar graphs with the same number of vertices.

Order (journal)

Order (subtitled "A Journal on the Theory of Ordered Sets and its Applications") is a quarterly peer-reviewed academic journal on order theory and its applications, published by Springer Science+Business Media.

Order dimension

In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.

Osculating circle

In differential geometry of curves, the osculating circle of a sufficiently smooth plane curve at a given point p on the curve has been traditionally defined as the circle passing through p and a pair of additional points on the curve infinitesimally close to p. Its center lies on the inner normal line, and its curvature is the same as that of the given curve at that point.

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.

Paul Koebe

Paul Koebe (15 February 1882 – 6 August 1945) was a 20th-century German mathematician.

Peripheral cycle

In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part.

Perspective (graphical)

Perspective (from perspicere "to see through") in the graphic arts is an approximate representation, generally on a flat surface (such as paper), of an image as it is seen by the eye.

Petersen family

In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6.

Planar separator theorem

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.

Planarity

Planarity is a puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University.

Planarity testing

In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections).

Planarization

In graph drawing, planarization is a method of extending drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.

Plane (geometry)

In mathematics, a plane is a flat, two-dimensional surface that extends infinitely far.

Plane curve

In mathematics, a plane curve is a curve in a plane that may be either a Euclidean plane, an affine plane or a projective plane.

Poland

Poland (Polska), officially the Republic of Poland (Rzeczpospolita Polska), is a country located in Central Europe.

Polyhedral graph

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron.

Regular polygon

In Euclidean geometry, a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).

Robertson–Seymour theorem

In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.

Scheinerman's conjecture

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.

Schlegel diagram

In geometry, a Schlegel diagram is a projection of a polytope from R^d into R^ through a point beyond one of its facets or faces.

Schnyder's theorem

In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets.

Simple polygon

In geometry a simple polygon is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pair-wise to form a closed path.

Sphere

A sphere (from Greek σφαῖρα — sphaira, "globe, ball") is a perfectly round geometrical object in three-dimensional space that is the surface of a completely round ball (viz., analogous to the circular objects in two dimensions, where a "circle" circumscribes its "disk").

Sprouts (game)

Sprouts is a paper-and-pencil game with significant mathematical properties.

Steinitz's theorem

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the (simple) 3-vertex-connected planar graphs (with at least four vertices).

Stereographic projection

In geometry, the stereographic projection is a particular mapping (function) that projects a sphere onto a plane.

Strangulated graph

In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph.

Thickness (graph theory)

In graph theory, the thickness of a graph is the minimum number of planar graphs into which the edges of can be partitioned.

Three utilities problem

The classical mathematical puzzle known as the three utilities problem; the three cottages problem or sometimes water, gas and electricity can be stated as follows: The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation.

Topological conjugacy

In mathematics, two functions are said to be topologically conjugate to one another if there exists a homeomorphism that will conjugate the one into the other.

Toroidal graph

In mathematics, a toroidal graph is a graph that can be embedded on a torus.

Torus

In geometry, a torus (plural tori) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis coplanar with the circle.

Tree (graph theory)

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.

Treewidth

In graph theory, the treewidth of an undirected graph is a number associated with the graph.

Universal point set

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.

Upward planar drawing

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.

Wagner's theorem

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).

Whitney's planarity criterion

In mathematics, Whitney's planarity criterion is a matroid-theoretic characterization of planar graphs, named after Hassler Whitney.

1-planar graph

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.

References

Hey! We are on Facebook now! »