Skip to main content

Representing Special Graphs

What This Concept Is​

Several graph families have so much extra structure that recognizing them unlocks faster or simpler algorithms. The ones that show up repeatedly in this module are:

  • DAG (directed acyclic graph). A directed graph with no directed cycles. Admits a topological order, linear-time shortest and longest paths, and DP over vertices.
  • Tree. A connected undirected graph with |V| - 1 edges and no cycles. Every tree is a sparse graph, and many tree problems collapse to a single DFS or BFS.
  • Forest. A disjoint union of trees. You get one whenever DFS runs on a graph that is not connected - the DFS tree edges form a spanning forest.
  • Bipartite graph. Vertices split into two sets L and R with every edge crossing the split. Detected with a 2-coloring BFS; enables matching algorithms via max flow.
  • Planar graph. A graph drawable on the plane without crossings. Satisfies Euler's formula |V| - |E| + |F| = 2 and has |E| <= 3|V| - 6, which bounds density.
  • Complete graph K_n. Every pair connected; |E| = n(n-1)/2. Useful as a worst-case density benchmark.
  • Sparse / dense. Not formal, but operational: sparse means |E| = O(|V|) (plus polylog), dense means |E| = Theta(|V|^2).

Each family comes with representations that exploit its structure: trees often carry a parent array; DAGs carry an in-degree array; bipartite graphs carry a side-label array; planar graphs carry a face list.

Why It Matters Here​

Recognition is operational, not decorative.

  • If you see a dependency graph, check for acyclicity first; if it is a DAG, you get topological sort, DP-based shortest paths, and CYK-style parsing for free.
  • If a problem pairs two sets of items and asks for a matching, you are in bipartite-graph land, and the question reduces to max flow.
  • If a graph is a tree, you do not need fancy shortest-path algorithms; a single DFS or BFS answers everything with O(|V|) work.
  • Planarity bounds |E| linearly in |V|, which tells you a dense adjacency matrix is wasteful and that four-coloring applies.

The shape of the graph tells you how much algorithm you need.

Concrete Example​

Consider assigning n students to n research projects where each student has listed 3 preferred projects.

  • Vertices split into two groups: students on the left, projects on the right. Edges go student -> project only. This is bipartite.
  • The question "can every student be assigned a preferred project?" is a perfect-matching question.
  • Because the graph is bipartite and sparse (|E| = 3n), you reduce to max flow on a source-sink graph with unit capacities and solve it in polynomial time.

If instead the graph had allowed student-student or project-project edges, matching would be the harder general-graph case (Edmonds' blossom algorithm) and the recipe would not fit.

Second example - a DAG of course prerequisites:

Because this is a DAG, a topological sort gives a legal course schedule in O(|V| + |E|). If a cycle existed (say cat -> calc), no schedule would exist and Kahn's algorithm would detect that in the same run.

Common Confusion / Misconceptions​

  • "Bipartite = two components." No. A bipartite graph is one whose vertices split so no edge stays inside either side. The two sides are usually still connected to each other through crossing edges.
  • "Acyclic" means the same in directed and undirected." An acyclic undirected graph is a tree or forest. An acyclic directed graph is a DAG - it can still have "diamonds" (two paths to the same vertex) that would be cycles if you ignored direction.
  • "A tree is just a sparse graph." Trees have rigid structure: exactly |V| - 1 edges, unique path between any two vertices, removing any edge disconnects them. None of these holds for a general sparse graph.
  • "Planar = drawable without visible crossings in your picture." The formal condition is existence of a planar embedding, not your Figma diagram. K_5 and K_{3,3} are the minimal non-planar graphs (Kuratowski).

How To Use It​

When you meet a new graph problem, run a quick structural checklist:

  1. Is it directed? If yes, is it acyclic? If yes, topological sort and DAG-DP are your tools.
  2. Do the vertices split naturally into two groups with all edges crossing? If yes, bipartite methods apply.
  3. Is |E| <= 3|V| - 6 (a hint at planarity or at least sparsity)? If yes, prefer list representations.
  4. Is there exactly |V| - 1 edges and it is connected? If yes, it's a tree - do not reach for Dijkstra.
  5. Is it a complete graph or close to it? Matrix representation + Floyd-Warshall is fine.

Structure recognition should happen before algorithm selection.

Transfer / Where This Shows Up Later​

Special-graph structure is the secret ingredient behind many later algorithms.

  • S3 (systems). Dependency graphs in build systems and linkers are DAGs; cycle detection is how make tells you your Makefile is broken.
  • S4 (compilers). SSA form turns the control flow graph into a reducible structure so every loop has a single header - this is a DAG-like property up to back edges.
  • S5 (OS). Scheduler dependency graphs are DAGs; cycle = deadlock.
  • S6 (databases). Query plans are DAGs (often trees). Bipartite graphs appear when matching queries to indexes or tables to partitions.
  • S7 (DDD). Context maps are directed graphs whose acyclicity across bounded contexts is a goal; fitness functions enforce DAG-ness.
  • S8 (distributed). Consistent-hashing rings are cycles by construction; leader-election spanning trees are, well, trees.

Back-link to S1 M2 where the definitions of tree, bipartite, and planar graphs are first introduced.

Check Yourself​

  1. How do you detect bipartiteness with BFS?
  2. Why does a DAG always have a topological order, and why does a directed graph with a cycle not?
  3. What is the densest a planar graph can be, and why does that matter for representation choice?
  4. What is the difference between a tree and a forest, and when would an algorithm return a forest?
  5. Prove that a connected undirected graph with |V| - 1 edges has no cycle (or cite the proof).

Mini Drill or Application​

Classify each graph (DAG, tree, bipartite, planar, general) and explain the structural evidence:

  1. Git commit graph (parent references).
  2. The interstate highway map of the contiguous US.
  3. A "follows" graph on a microblog where each user follows arbitrarily.
  4. A student-class enrollment graph.
  5. A family tree restricted to biological ancestry.
  6. The Rubik's cube state graph under legal moves.

For at least two of them, sketch how you would verify the classification algorithmically in O(|V| + |E|).

Implementation drill. Write three small utilities on top of your Graph class: is_dag(g) (uses topo sort or DFS back-edge check), is_bipartite(g) (2-coloring BFS), and is_tree(g) (exactly |V| - 1 edges and connected). Run them on 10 random graphs and hand-verify the labels.

Read This Only If Stuck​