Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 

Planar graph

Index 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. [1]

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, ..., Kuratowski's theorem, Left-right planarity test, Line (geometry), Line graph, Line segment, Linking number, Linkless embedding, Mac Lane's planarity criterion, Map graph, Mathematical induction, Meshedness coefficient, Order (journal), Order dimension, Osculating circle, Outerplanar graph, Paul Koebe, Peripheral cycle, Perspective (graphical), Petersen family, Planar separator theorem, Planarity, Planarity testing, Planarization, Plane (geometry), Plane curve, Poland, Polyhedral graph, Regular polygon, Robertson–Seymour theorem, Scheinerman's conjecture, Schlegel diagram, Schnyder's theorem, Simple polygon, Sphere, Sprouts (game), Steinitz's theorem, Stereographic projection, Strangulated graph, Thickness (graph theory), Three utilities problem, Topological conjugacy, Toroidal graph, Torus, Tree (graph theory), Treewidth, Universal point set, Upward planar drawing, Wagner's theorem, Whitney's planarity criterion, 1-planar graph. Expand index (50 more) »

Algorithm

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

New!!: Planar graph and Algorithm · See more »

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.

New!!: Planar graph and Apex graph · See more »

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.

New!!: Planar graph and Apollonian network · See more »

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.

New!!: Planar graph and Big O notation · See more »

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.

New!!: Planar graph and Branch-decomposition · See more »

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.

New!!: Planar graph and Butterfly graph · See more »

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.

New!!: Planar graph and Chordal graph · See more »

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.

New!!: Planar graph and Circle packing theorem · See more »

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.

New!!: Planar graph and Circuit rank · See more »

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.

New!!: Planar graph and Clique-sum · See more »

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.

New!!: Planar graph and Colin de Verdière graph invariant · See more »

Combinatorial map

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

New!!: Planar graph and Combinatorial map · See more »

Complete bipartite graph

No description.

New!!: Planar graph and Complete bipartite graph · See more »

Complete graph

No description.

New!!: Planar graph and Complete graph · See more »

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.

New!!: Planar graph and Connectivity (graph theory) · See more »

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.

New!!: Planar graph and Convex polygon · See more »

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.

New!!: Planar graph and Convex polytope · See more »

Cycle (graph theory)

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

New!!: Planar graph and Cycle (graph theory) · See more »

Cycle space

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

New!!: Planar graph and Cycle space · See more »

David Bader (computer scientist)

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.

New!!: Planar graph and David Bader (computer scientist) · See more »

Dense graph

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

New!!: Planar graph and Dense graph · See more »

Directed acyclic graph

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

New!!: Planar graph and Directed acyclic graph · See more »

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.

New!!: Planar graph and Dual graph · See more »

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.

New!!: Planar graph and Equivalence class · See more »

Euler characteristic

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

New!!: Planar graph and Euler characteristic · See more »

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.

New!!: Planar graph and Fáry's theorem · See more »

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.

New!!: Planar graph and Forbidden graph characterization · See more »

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.

New!!: Planar graph and Four color theorem · See more »

Genus (mathematics)

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

New!!: Planar graph and Genus (mathematics) · See more »

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.

New!!: Planar graph and Geometric graph theory · See more »

Glossary of graph theory terms

This is a glossary of graph theory terms.

New!!: Planar graph and Glossary of graph theory terms · See more »

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".

New!!: Planar graph and Graph (discrete mathematics) · See more »

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.

New!!: Planar graph and Graph coloring · See more »

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.

New!!: Planar graph and Graph embedding · See more »

Graph isomorphism problem

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

New!!: Planar graph and Graph isomorphism problem · See more »

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.

New!!: Planar graph and Graph minor · See more »

Graph theory

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

New!!: Planar graph and Graph theory · See more »

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.

New!!: Planar graph and Halin graph · See more »

Hanani–Tutte theorem

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

New!!: Planar graph and Hanani–Tutte theorem · See more »

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.

New!!: Planar graph and Homeomorphism · See more »

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'.

New!!: Planar graph and Homeomorphism (graph theory) · See more »

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.

New!!: Planar graph and If and only if · See more »

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.

New!!: Planar graph and Integer lattice · See more »

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.

New!!: Planar graph and Intersection graph · See more »

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.

New!!: Planar graph and Isomorphism · See more »

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.

New!!: Planar graph and Journal of Graph Algorithms and Applications · See more »

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.

New!!: Planar graph and K-tree · See more »

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.

New!!: Planar graph and K-vertex-connected graph · See more »

Kazimierz Kuratowski

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

New!!: Planar graph and Kazimierz Kuratowski · See more »

Klaus Wagner

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

New!!: Planar graph and Klaus Wagner · See more »

Kuratowski's theorem

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

New!!: Planar graph and Kuratowski's theorem · See more »

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.

New!!: Planar graph and Left-right planarity test · See more »

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.

New!!: Planar graph and Line (geometry) · See more »

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.

New!!: Planar graph and Line graph · See more »

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.

New!!: Planar graph and Line segment · See more »

Linking number

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

New!!: Planar graph and Linking number · See more »

Linkless embedding

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.

New!!: Planar graph and Linkless embedding · See more »

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.

New!!: Planar graph and Mac Lane's planarity criterion · See more »

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.

New!!: Planar graph and Map graph · See more »

Mathematical induction

Mathematical induction is a mathematical proof technique.

New!!: Planar graph and Mathematical induction · See more »

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.

New!!: Planar graph and Meshedness coefficient · See more »

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.

New!!: Planar graph and Order (journal) · See more »

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.

New!!: Planar graph and Order dimension · See more »

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.

New!!: Planar graph and Osculating circle · See more »

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.

New!!: Planar graph and Outerplanar graph · See more »

Paul Koebe

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

New!!: Planar graph and Paul Koebe · See more »

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.

New!!: Planar graph and Peripheral cycle · See more »

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.

New!!: Planar graph and Perspective (graphical) · See more »

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.

New!!: Planar graph and Petersen family · See more »

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.

New!!: Planar graph and Planar separator theorem · See more »

Planarity

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

New!!: Planar graph and Planarity · See more »

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).

New!!: Planar graph and Planarity testing · See more »

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.

New!!: Planar graph and Planarization · See more »

Plane (geometry)

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

New!!: Planar graph and Plane (geometry) · See more »

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.

New!!: Planar graph and Plane curve · See more »

Poland

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

New!!: Planar graph and Poland · See more »

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.

New!!: Planar graph and Polyhedral graph · See more »

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).

New!!: Planar graph and Regular polygon · See more »

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.

New!!: Planar graph and Robertson–Seymour theorem · See more »

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.

New!!: Planar graph and Scheinerman's conjecture · See more »

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.

New!!: Planar graph and Schlegel diagram · See more »

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.

New!!: Planar graph and Schnyder's theorem · See more »

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.

New!!: Planar graph and Simple polygon · See more »

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").

New!!: Planar graph and Sphere · See more »

Sprouts (game)

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

New!!: Planar graph and Sprouts (game) · See more »

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).

New!!: Planar graph and Steinitz's theorem · See more »

Stereographic projection

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

New!!: Planar graph and Stereographic projection · See more »

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.

New!!: Planar graph and Strangulated graph · See more »

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.

New!!: Planar graph and Thickness (graph theory) · See more »

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.

New!!: Planar graph and Three utilities problem · See more »

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.

New!!: Planar graph and Topological conjugacy · See more »

Toroidal graph

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

New!!: Planar graph and Toroidal graph · See more »

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.

New!!: Planar graph and Torus · See more »

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.

New!!: Planar graph and Tree (graph theory) · See more »

Treewidth

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

New!!: Planar graph and Treewidth · See more »

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.

New!!: Planar graph and Universal point set · See more »

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.

New!!: Planar graph and Upward planar drawing · See more »

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).

New!!: Planar graph and Wagner's theorem · See more »

Whitney's planarity criterion

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

New!!: Planar graph and Whitney's planarity criterion · See more »

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.

New!!: Planar graph and 1-planar graph · See more »

Redirects here:

Convex plane graph, Kuratowski's reduction theorem, Maximal planar graph, Nonplanar graph, Outer planar graph, Outplanar graph, Planar Graph, Planar embedding, Planar embedding of the graph, Planar graphs, Planar map, Planarity (graph theory), Plane graph, Planer graph, Pontryagin-Kuratowski theorem, Pontryagin–Kuratowski theorem, Theorem P, Triangular graph, Wagner theorem.

References

[1] https://en.wikipedia.org/wiki/Planar_graph

OutgoingIncoming
Hey! We are on Facebook now! »