Graph embedding

From Wikipedia, the free encyclopedia

You have new messages (last change).

In Topological graph theory, an embedding of a graph G on a surface (which stands here for a compact arc-connected Hausdorff space locally homeomorphic to a disk) Σ is the equivalence class (for homeomorphism) of representations of G on Σ in which points are associated to vertices, simple arcs (homeomorphic images of [0;1]) are associated to edges in such a way that:

  • the endpoints of the arc associated to an edge e are the points associated to the end vertices of e,
  • an arc include no points associated with other vertices,
  • two arcs never intersect at a point which is interior to one of the arc.

If a graph G is embedded on a closed surface Σ, the complement of the union of the points and arcs associated to the vertices and edges of G is a familly of regions (or faces). A 2-cell embedding is an embedding in which every face is homeomorphic to an open disk.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../g/r/a/Graph_embedding.html"