Testing whether or not a graph is planar is an important aspect of graph theory. Wagner’s Theorem provides a characterization of planar graphs based on graph minors. 512 more words

## Tags » Planar Graphs

#### A few interesting open problems

- Does the class of constant-degree expanders have polynomially-long induced paths?
- Planar embedding conjecture — Can every planar graph equipped with an arbitrary shortest-path metric be embedded into L1 with only a constant distortion? 65 more words

#### Boron and Buckyballs

Recent news from the world of chemistry: the result is really the experimental observation of a special new molecule. People call it a “Boron Buckyball”, but this irritates me since we know that the buckyball is a specific fullerene on 60 vertices. 840 more words

#### Euler-Poincaré characteristic (I): Euler's formula and graph theory

This is the introductory note of a sequence of notes dedicated to Euler-Poincaré characteristic. Here, we deal with Euler’s formula from a graph theoritical viewpoint and exhibit several applications including a proof of Pick’s theorem and the classification of Plato’s solids. 1,157 more words

#### From Euler Characteristics to Cohomology (I)

[ *Warning: this is primarily an expository article, so the proofs are not airtight, but they should be sufficiently convincing*. ]

The five platonic solids were well-known among the ancient Greeks ( 1,685 more words

#### Lecture 26: 03/30/2012

First, a restatement of the HW. I’ll update the post about HW 6 soon so look for that.

Today, we wrapped up the presentation of the polynomial-time planarity algorithm outlined in Wednesday’s lecture. 88 more words

#### Lecture 25: 03/28/2012

More Planarity.

We have a new HW assignment due next Wednesday. I’ll make a separate post for it.

How do we represent a planar graph? Well, I could tell you that a graph is planar, but that does you no good. 321 more words