PrevNext
Rare
 0/6

Euler's Formula

Authors: Benjamin Qi, Aarush Penugonda

A formula for finding the number of faces in a planar graph.

Introduction

A planar graph is a graph that can be drawn on a plane without any edges crossing. In other words, it can be embedded in the plane such that no two edges intersect except at their endpoints. Planar graphs can be represented in a two-dimensional space without overlaps between edges.

Resources
MIT

6.024J course notes

Wiki

Wiki Definition

Rutgers

Euler's Formula

Euler's Formula states that any correct embedding of a connected planar graph satistfies:-

V − E + F = 2

Where V is the no of vertices, E is the number of edges and F is the number of faces.

Example 1

StatusSourceProblem NameDifficultyTags
APIOVery Hard
Show Tags2DRQ, Euler's Formula, Persistent Segtree

Explanation

Intuition

In this problem, we're asked to count the number of contiguous areas of cells on several flat rectangles. Such areas are separated by river segments and rectangle boundaries.

Where else do we count the number of areas on a flat surface?

That's right - we use Euler's formula to count the number of faces of a planar graph. This suggests that we should turn our rectangles into planar graphs.

Making the Planar Graph

We can turn a rectangle into a planar graph as so:

  • Put temporary river segments outside the border of the rectangle.
  • For each river segment, we insert its 4 corners into a set of nodes and its 4 sides into a set of edges.

Notice how the resulting graph is planar, so we can apply Euler's formula.

Applying Euler's Formula

For a planar graph, Euler's formula is given as F=EV+1+CF = E - V + 1 + C, where FF is the number of faces (including the background face), EE is the number of edges, VV is the number of vertices, and CC is the number of connected components.

Notice how FF in our planar graph is equal to 1+R+A1 + R + A, where RR is the number of river segments and AA is the answer to the query. This means we must subtract R+1R + 1 from FF to get AA.

Since the whole river is a big connected component, we can just check whether the river touches the bounding rectangle to determine CC.

Finding EE, VV, and RR is a lot more complicated though.

Finding EE, VV, and RR

To find EE, VV, and RR, we can use a data structure that can handle 2D range queries efficiently.

However, the coordinates of the grid can get very large, so a simple 2D BIT or segment tree won't work here.

To work around this, we can either use a 2D BIT with coordinate compression or a persistent segment tree. See the sections on offline 2D sum queries or persistent segment trees for more details.

Implementation

With a persistent segment tree.

Time Complexity: O(NlogN)\mathcal{O}(N \log N)

Memory Complexity: O(NlogN)\mathcal{O}(N \log N)

#include "rainbow.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
const int MAXN = 2e5, MAXSEG = (6e5 + 9) * 19 + 1;
int cnt = 1, segtree[MAXSEG], left_c[MAXSEG], right_c[MAXSEG];
struct Segtree {

Example 2

StatusSourceProblem NameDifficultyTags
PlatinumVery Hard

Explanation

This problem involves a 2D grid. The code tracks connected region of points using heights. We will use Disjoint Set Union (DSU). As we process points by increasing height, we merge them into regions and update the answer based on their size. The logic here mirrors an application of Euler's formula for planar graphs, where we maintain boundaries (faces) as we mege points (vertices) and check their connectivity (edges).

Implementation

With Euler's Formula

Time Complexity: O(N2logN)\mathcal{O}(N^2 \log N)

Memory Complexity: O(N2)\mathcal{O}(N^2)

int N, h[750][750];
ll ans;
vector<pair<int, pi>> v;
int hsh(int a, int b) { return N * a + b; }
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
template <int SZ> struct DSU {
int par[SZ], sz[SZ], measure[SZ];

Problems

StatusSourceProblem NameDifficultyTags
KattisVery Hard
Show TagsDSU, Euler's Formula
CFVery Hard
Show TagsEuler's Formula, FFT
CFVery Hard
Show TagsEuler's Formula
PlatinumVery Hard
Show TagsEuler's Formula

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext