请输入您要查询的字词:

 

单词 PlanarGraph
释义

planar graph

\\xyoption

all

Description

A planar graphMathworldPlanetmath is a graph which can be drawn on a plane (a flat 2-d surface) or on a sphere, with no edges crossing. When drawn on a sphere, the edges divide its area in a number of regions called faces (or “countries”, in the context of map coloring). When drawn on a plane, there is one outer country taking up all the space outside the drawing. Every graph drawn on a sphere can be drawn on a plane (puncture the sphere in the interior of any one of the countries) and vice versa. Statements on map coloring are often simpler in terms of a spherical map because the outer country is no longer a special case.

The number of faces (countries) equals c+1 where c is the cyclomatic number, c=m-n+k (where m is the number of edges, n the number of vertices, and k the number of connected componentsMathworldPlanetmathPlanetmathPlanetmath of the graph). All this holds equally for planar multigraphsMathworldPlanetmath and pseudographsMathworldPlanetmath.

No complete graphsMathworldPlanetmath above K4 are planar. K4, drawn without crossings, looks like :

\\xymatrix&A\\ar@-[d]\\ar@-[ddl]\\ar@-[ddr]&&B\\ar@-[dl]\\ar@-[dr]&C\\ar@-[rr]&&D

Hence it is planar (try this for K5.)

A drawing of a planar graph is a drawing in which each edge is drawn as a line segmentMathworldPlanetmath. Every planar graph has a drawing. This result was found independently by Wagner, Fáry and Stein. Schnyder improved this further by showing how to draw any planar graph with n vertices on an integer grid of O(n2) area.

Definition

Ideally, this definition would just formalize what was described above. It will not, exactly. It will formalize the notion of a graph with an embeddingMathworldPlanetmath into the plane.

Definition.

Let M be a topological manifoldMathworldPlanetmathPlanetmath. Then a graph on M is a pair (G,ι), where

  1. 1.

    G is a multigraph,

  2. 2.

    ι is a function from the graph topology of G into M, and

  3. 3.

    ι is a homeomorphismMathworldPlanetmathPlanetmath onto its image.

A plane graph is a graph on 2.

A planar graph is a graph G that has an embedding ι making (G,ι) into a plane graph.

Normally, the only manifolds M that are of interest are two-dimensional.

The most usual question for which this definition finds a use is “can the following graph G be made into a graph on M?”. When M is the plane, this is usually phrased as “Is G a planar graph?”. Wagner’s theorem provides a criterion for answering this question. When M is a torus, the answer changes: the complete bipartite graphMathworldPlanetmath K3,3 can be made into a graph on the torus.

A graph on a manifold has a notion of “face” as well as the usual graph notions of vertex and edge.

Titleplanar graph
Canonical namePlanarGraph
Date of creation2013-03-22 12:17:37
Last modified on2013-03-22 12:17:37
Ownerarchibal (4430)
Last modified byarchibal (4430)
Numerical id12
Authorarchibal (4430)
Entry typeDefinition
Classificationmsc 05C10
Synonymplanar
Related topicWagnersTheorem
Related topicKuratowskisTheorem
Related topicCrossingLemma
Related topicCrossingNumber
Related topicFourColorConjecture
Definesplane graph
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 2:50:52