Book contents
- Frontmatter
- Contents
- Foreword
- Preface
- Introduction
- 1 Embedding graphs on surfaces
- 2 Maximum genus
- 3 Distribution of embeddings
- 4 Algorithms and obstructions for embeddings
- 5 Graph minors: generalizing Kuratowski's theorem
- 6 Colouring graphs on surfaces
- 7 Crossing numbers
- 8 Representing graphs and maps
- 9 Enumerating coverings
- 10 Symmetric maps
- 11 The genus of a group
- 12 Embeddings and geometries
- 13 Embeddings and designs
- 14 Infinite graphs and planar maps
- 15 Open problems
- Notes on contributors
- Index
8 - Representing graphs and maps
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Foreword
- Preface
- Introduction
- 1 Embedding graphs on surfaces
- 2 Maximum genus
- 3 Distribution of embeddings
- 4 Algorithms and obstructions for embeddings
- 5 Graph minors: generalizing Kuratowski's theorem
- 6 Colouring graphs on surfaces
- 7 Crossing numbers
- 8 Representing graphs and maps
- 9 Enumerating coverings
- 10 Symmetric maps
- 11 The genus of a group
- 12 Embeddings and geometries
- 13 Embeddings and designs
- 14 Infinite graphs and planar maps
- 15 Open problems
- Notes on contributors
- Index
Summary
Motivated by graph drawing problems, we can formulate a theory of graph representations precisely, admitting various generalizations. Each vertex is represented as a point in Euclidean space and each edge as a line segment spanned by the representations of its endpoints. A typical problem in this area is finding an optimal graph representation that minimizes a given energy function. For some parameters this problem admits an exact solution while other parameters require iterative methods. Representations of graphs are then extended to representations of maps and other incidence geometries.
Introduction
One reason why the pure combinatorial structure of a graph is so interesting and attracts the attention of many researchers lies in the fact that a graph can usually be completely defined geometrically. On the other hand, some physical and geometrical objects, such as molecules and polyhedra, carry a graph structure. Usually a graph is depicted by placing its vertices in the plane (or in 3-space) and joining the points corresponding to adjacent vertices of the graph with line segments or simple curves. Based on this idea we make the notion of graph representation precise.
The notion of graph representation was first used implicitly in the work of Steinitz [45], Wagner [49], Fáry [14] and Stein [43]. They produced the following fundamental results in the theory of simple planar graphs.
Theorem 1.1 (Steinitz' theorem) A graph is planar and 3-connected if and only if it is the graph of a convex 3-dimensional polyhedron.
Theorem 1.2 (Fáry’s theorem)Every planar graph can be represented in the plane without edge crossings with line segments for edges.
- Type
- Chapter
- Information
- Topics in Topological Graph Theory , pp. 151 - 180Publisher: Cambridge University PressPrint publication year: 2009
- 5
- Cited by