Articles of planar graph

Analogue of Fáry's theorem taking sphere and geodesics instead of plane and straight lines.

Fary’s theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments (see Wikipedia). The proof is based on the Art gallery theorem, so I would have asked also this latter. But, perhaps there is a simpler answer on my question. In any case, my question […]

Prove that the tesseract graph is non-planar

The tesseract graph may be defined in various ways. I’m thinking of it as a subset lattice of the set $\{a,b,c,d\}$, where two subsets are adjacent if they differ in size by one, and one contains the other. The tesseract is listed as non-planar on Wolfram MathWorld, but there is no proof given. I’m trying […]

Consequences of cycle space cut space duality

The cycle space cut space duality theorem for planar graphs states that: The cycle space of a planar graph is the cut space of its dual graph, and vice versa. I wish to know any consequences and applications of this result with possible proofs or references to them.

A space curve is planar if and only if its torsion is everywhere 0

Can someone please explain this proof to me. I know that a circle is planar and has nonzero constant curvature, so this must be an exception, but I am a little lost on the proof. Thanks!

Can there exist an uncountable planar graph?

I’m currently revising a course on graph theory that I took earlier this year. While thinking about planar graphs, I noticed that a finite planar graph corresponds to a (finite) polygonisation of the Euclidean plane (or whichever surface you’re working with). By considering, for example a full triangulation of the plane, you can find an […]

Partitioning the edges of $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs

Why is it impossible to partition the edges in $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs for $n \ge 6$? I’m just stuck at the beginning and can’t figure out how to go about this problem. Thanks in advance for the help!

Scalene rectangulation of a square: let me count the ways

A rectangulation of a square is a dissection of the square $S$ into smaller rectangles $R_i$, $i=1,\ldots,n$ with the usual caveats: $S = \cup_i R_i$ and the interiors of distinct rectangles $R_i,R_j$ are disjoint. We say a rectangulation is scalene if distinct rectangles (including the square $S$) do not have equal length sides of either […]

Use Gröbner bases to count the $3$-edge colorings of planar cubic graphs…

I found a nice introduction on how to Use Gröbner bases to construct the colorings of a finite graph. Now my graphs $G=(V,E)$ are the line graphs planar of cubic graphs, so they are $4$-regular. The corresponding edge-adjacency matrices can be constructed, as shown here (in a crude way, I admit…). Planarity assures the existence […]

How to count the closed left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed path on $\Gamma$ such that, at each vertex, the path turns left in the orientation $\mathcal O$. I want to calculate […]

3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of vertices, edges and faces of degree 4 and 6. Using handshake lemmas and Euler Formula, I’ve come up […]