Drawing graphs

Embeddings:

• circular embedding — vertices are spaced evenly around a circle
• ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking

Planar graphs: graphs where no edges cross

• interior region: empty space enclosed by a cycle
• exterior region: empty space not enclosed by a cycle
• Euler’s formula for planar graphs:
  • n-m+r=2
  • n vertices, m edges, r regions
• condition for planar graph: m ≤ 3v-6
• every planar graph has a vertex *v, *with δ(v) ≤ 5