Planar facial graph facts and isomorphism extension for arbitrary arc drawings

Let $G$ be drawn. The drawing $X$ is a finite union of arcs together with finitely many points, hence compact, and closed in the plane by [L3]. If two arcs have the same two distinct endpoints and meet exactly at those endpoints, their union is a Jordan curve: parametrizing the circle by the two arcs and identifying the four endpoint parameters gives a continuous bijection from the compact circle onto the union, which is a homeomorphism by [L3]. Consequently every cycle of a drawn graph is a Jordan curve, since its edges paste successively in this way; in particular, if $J$ is a Jordan curve, $p\mathrm{\ne }q$ lie in $J$ and $Q$ is an arc with $Q\cap J=\{p,q\}$, then the two unions $D_i=J_i\cup Q$ of $Q$ with the two closed arcs $J_1,J_2$ of $J$ from $p$ to $q$ are Jordan curves.

Drawings are finite CW complexes. On the abstract graph make a CW structure with the vertices as $0$-cells and the edges as $1$-cells attached by their endpoint maps, and let $\mathrm{\mid }G\mathrm{\mid }$ be the resulting finite CW complex; the drawing map that sends each edge parameter to its arc and each vertex to its point is continuous on the finite closed cover by the edge closures and is a bijection because edges meet only at common endpoints. Since $\mathrm{\mid }G\mathrm{\mid }$ is a finite union of compact closed cells it is compact, so [L3] makes the drawing map a homeomorphism and $X$ a finite CW complex with $V$ $0$-cells, $E$ $1$-cells and no higher cells. Every point of $X$ has a neighbourhood basis of contractible neighbourhoods: open subintervals at interior points of edges, and at a vertex $v$ the open stars formed by initial segments of the incident edges, which are open because their preimages in the disjoint union of edges are unions of half-open intervals, and which contract to $v$ by sliding each initial segment along itself; a homeomorphism preserves this, so every drawing is weakly locally contractible in the sense of [F6]. If $G$ is connected, then $X$ is path connected: any two vertices are joined by a path in $G$ whose edges patch to a continuous path, and every point of $X$ is a vertex or lies on an edge. Conversely, the trace of each graph component is closed, being a finite union of compact arcs and vertices; its complement in $X$ is also such a finite union, so it is open as well. A connected path image cannot meet two of these disjoint clopen traces. Hence the path components of $X$ are exactly the $c$ connected components of $G$.

Facial cycles: base of the induction. Every finite connected graph has a spanning tree and every finite $2$-connected graph has an ear decomposition beginning with any specified cycle, by [F3]. Let $G$ be $2$-connected, build the drawing by the ear decomposition from any cycle $C_0$, and induct on the number of ears with the invariants: (I0) each face is the region of its frontier cycle, that is the component of the complement of that cycle containing it; (I1) the frontier of every face is the point set of a cycle of the current drawing; (I2) the sum of the lengths of the facial boundary cycles equals twice the number of drawn edges. For the initial cycle $C_0$, always a simple cycle, [F1] gives exactly two regions with frontier $C_0$, so (I0) and (I1) hold with both facial boundaries the cycle $C_0$, and each of the two faces traverses all $E$ cycle edges once, giving total boundary length $2E$, which is (I2).

Homology of a drawing. Let $X$ be a drawing with $V$ vertices, $E$ edges and $c$ components. By step 1.2 it is a finite CW complex with exactly $V$ $0$-cells, $E$ $1$-cells and no cells of dimension $\ge 2$, so its Euler characteristic is $\chi (X)=V-E$, and all singular homology of $X$ vanishes in degrees $\ge 2$, because cellular homology computes singular homology and the cellular chain complex is concentrated in degrees $0$ and $1$. The Euler-Poincare formula therefore gives $V-E=\mathrm{rank}{H}_0(X;\mathbb{Z})-\mathrm{rank}{H}_1(X;\mathbb{Z})$; the group $H_0(X;\mathbb{Z})$ is free on the path components of $X$, which number $c$ by step 1.2, so $\mathrm{rank}{H}_1(X;\mathbb{Z})=E-V+c$. Moreover $H_1(X;\mathbb{Z})=\ker d_1$ is a subgroup of the free group $C_1={\mathbb{Z}}^E$, hence is free of rank at most $E$ and finitely generated, and $\mathrm{rank}{H}_1(X;\mathbb{Z})$ is its intrinsic rank.

Crosscut: structure. Let $J$ be a Jordan curve with complementary regions $V$ and $W$, let $p\mathrm{\ne }q$ be points of $J$, and let $Q$ be an arc with $Q\cap J=\{p,q\}$ and $Q^{\circ }\subseteq V$. By step 1.1 the two curves $D_i=J_i\cup Q$ are Jordan curves, where $J_1,J_2$ are the two closed arcs of $J$ from $p$ to $q$. By [F1] each $D_i$ has exactly two complementary regions with frontier $D_i$; let $Z_i$ be the region of ${\mathbb{R}}^2\setminus D_i$ containing $W$, well defined because $W$ is connected and disjoint from $D_i$, and let $Y_i$ be the other region. Every point of $J\setminus J_i$ lies in $Z_i$: such a point $x$ has a ball $B$ about it disjoint from $D_i$ and meeting $W$, because $x$ lies in the frontier $J$ of $W$, and since $B$ is connected and avoids $D_i$ it lies in $Z_i$. Hence $Y_i$ misses $J_i$ and $J\setminus J_i$, so $Y_i$ misses $J$; being connected it lies in one region of ${\mathbb{R}}^2\setminus J$, and it is not $W$ because $W\subseteq Z_i$ and $Y_i\cap Z_i=\mathrm{\varnothing }$, so $Y_i\subseteq V$. Next $Y_2\subseteq Z_1$: the set $Y_2$ misses $Q\subseteq D_2$ and misses $J$, so it lies in ${\mathbb{R}}^2\setminus D_1$; and points of $Y_2$ are arbitrarily close to each point of the open arc $J_2^{\circ }$, because the frontier of $Y_2$ is $D_2$; that arc lies in $J\setminus J_1\subseteq Z_1$, and $Z_1$ is open, so $Y_2$ meets $Z_1$ and therefore lies in $Z_1$. Symmetrically $Y_1\subseteq Z_2$, so $Y_1\cap Y_2=\mathrm{\varnothing }$. Since $Y_i$ is open in the plane and its frontier $D_i$ is disjoint from $\mathrm{\Omega }:={\mathbb{R}}^2\setminus (J\cup Q)$, each $Y_i$ is open and closed in $\mathrm{\Omega }$; the set $Z_1\cap Z_2$ is open, nonempty because it contains $W$, and $\mathrm{\Omega }=Y_1\bigsqcup Y_2\bigsqcup (Z_1\cap Z_2)$, because $\mathrm{\Omega }=(Y_1\bigsqcup Z_1)\cap \mathrm{\Omega }$ and $Z_1\cap \mathrm{\Omega }=Z_1\cap ({\mathbb{R}}^2\setminus D_2)=Y_2\bigsqcup (Z_1\cap Z_2)$.

Complement components by duality. Let $K\subseteq {\mathbb{R}}^2$ be nonempty, compact and weakly locally contractible, and identify ${\mathbb{R}}^2$ with $S^2\setminus \{\mathrm{\infty }\}$ by the explicit stereographic homeomorphism $x\mapsto (2x_1\mathrm{/}(1+\mathrm{\mid }x{\mathrm{\mid }}^2),2x_2\mathrm{/}(1+\mathrm{\mid }x{\mathrm{\mid }}^2),(\mathrm{\mid }x{\mathrm{\mid }}^2-1)\mathrm{/}(1+\mathrm{\mid }x{\mathrm{\mid }}^2))$, whose inverse from the sphere minus the north pole is $(X_1,X_2,X_3)\mapsto (X_1\mathrm{/}(1-X_3),X_2\mathrm{/}(1-X_3))$. The sphere is the one specified by [F7]. Hence $K$ is a nonempty proper compact subset of $S^2$, bounded and missing the point at infinity by [L3], and weakly locally contractible in $S^2$ because near a point of $K$ the spherical and planar neighbourhoods agree. By [F6] with $n=2$, $i=0$ and $R=\mathbb{Z}$, ${\tilde{H}}_0(S^2\setminus K;\mathbb{Z})\cong {\tilde{H}}^1(K;\mathbb{Z})=H^1(K;\mathbb{Z})$, the last equality because $K$ is nonempty. By [F5], $H^1(K;\mathbb{Z})\cong \mathrm{Hom}(H_1(K;\mathbb{Z}),\mathbb{Z})$ because ${\mathrm{Ext}}^1(H_0(K;\mathbb{Z}),\mathbb{Z})=0$ as $H_0$ is free, so by [L6] the rank of $H^1(K;\mathbb{Z})$ equals $\mathrm{rank}{H}_1(K;\mathbb{Z})$ whenever $H_1(K;\mathbb{Z})$ is finitely generated. Also by [F5], ${\tilde{H}}_0(S^2\setminus K;\mathbb{Z})$ is free on the set of path components of $S^2\setminus K$ modulo one, and by [L4] applied to the locally path connected spaces ${\mathbb{R}}^2\setminus K$ and $S^2\setminus K$ these path components are their components, so its rank is the number of components of $S^2\setminus K$ minus one. The components of ${\mathbb{R}}^2\setminus K$ and of $S^2\setminus K$ are in bijection: writing $e$ for the point at infinity, for every component $C$ of $S^2\setminus K$ the set $C\setminus \{e\}$ is connected, because it equals $C$ when $e\mathrm{\notin }C$, and if $e\in C$ and $C\setminus \{e\}=A\bigsqcup B$ were a separation into nonempty relatively clopen sets, choose $r$ with $K$ in the closed ball of radius $r$. The outer cap $N\cup \{e\}$, with $N=\{x:\mathrm{\mid }x\mathrm{\mid }>r\}$, is connected, lies in $S^2\setminus K$ and contains $e$, hence $N\subseteq C\setminus \{e\}$. Thus connected $N$ lies wholly in, say, $A$. Consequently $B$ lies in the closed radius-$r$ ball and $e$ is not in its closure in $C$. As $B$ is already relatively open and closed in $C\setminus \{e\}$, it is now open and closed in connected $C$, a contradiction; and $C\mapsto C\setminus \{e\}$ is a bijection onto the components of ${\mathbb{R}}^2\setminus K$, since a component of ${\mathbb{R}}^2\setminus K$ is connected in $S^2\setminus K$ and lies in a unique component $C$, which yields it back. Comparing ranks, $\mathrm{\#}\{\text{faces of }X\}=1+\mathrm{rank}{H}_1(X;\mathbb{Z})$ for every nonempty drawing $X$; inserting step 2.1 gives $F=1+E-V+c$, that is $V-E+F=1+c$; for the empty graph $V=E=c=0$ and $F=1$, so the same formula holds. Applied to the theta curve $\theta$ formed by a Jordan curve $J$ and an arc $Q$ with $Q\cap J=\{p,q\}$ and $Q^{\circ }\cap J=\mathrm{\varnothing }$, first subdivide each of its three $p$-to-$q$ arcs once at a distinct free point. This is a drawing of the simple graph $K_{2,3}$ with $V=5$, $E=6$ and $c=1$, the geometric trace and complement unchanged. Steps 1.1 and 1.2 therefore give $\mathrm{\#}{\pi }_0({\mathbb{R}}^2\setminus \theta )=1+(6-5+1)=3$. In particular a connected drawing satisfies $V-E+F=2$, which proves (b).

Crosscut: the count. With $\theta =J\cup Q$ as in step 3.1, the space $\mathrm{\Omega }$ is the disjoint union of the three open sets $Y_1,Y_2$ and $Z_1\cap Z_2$ by step 2.2, and step 3.1 gives $\mathrm{\#}{\pi }_0(\mathrm{\Omega })=3$. The sets $Y_1,Y_2$ are nonempty connected open and closed subsets of $\mathrm{\Omega }$, so each is a component, and therefore $Z_1\cap Z_2$ is also connected. Since $\mathrm{\Omega }=(V\setminus Q)\bigsqcup W$ is a separation into open sets with $W$ connected, the components of $\mathrm{\Omega }$ are those of $V\setminus Q$ together with $W$; as $Y_1\cup Y_2\subseteq V\setminus Q$ are two distinct components, $V\setminus Q=Y_1\bigsqcup Y_2$ and $Z_1\cap Z_2=W$. Thus ${\mathbb{R}}^2\setminus (J\cup Q)$ has exactly the three components $W,Y_1,Y_2$, with frontiers $J,D_1,D_2$, and the two regions of $V\setminus Q$ have the Jordan curves $D_1,D_2$ as frontiers.

Facial cycles: the ear step. Let the current drawing $X_H$ of the $2$-connected graph $H$ satisfy (I0), (I1) and (I2) and let $Q$ be the next ear, a path with distinct endpoints $u\mathrm{\ne }v$ on $X_H$ whose relative interior is disjoint from $X_H$. The relative interior of $Q$ is connected and lies in the complement of $X_H$, so it lies in a single face $F$, and $F$ is the region of the Jordan curve $J=\mathrm{Fr}(F)$ containing it by (I0) and (I1). The endpoints $u,v$ lie in $J$, because points of $Q$ near each of them lie in $F$ and $J=\mathrm{Fr}(F)$; the two closed arcs $J_1,J_2$ of $J$ from $u$ to $v$ are graph paths, so $D_i=J_i\cup Q$ are graph cycles, hence Jordan curves. By step 4.1 the new drawing $X_H\cup Q$ has exactly the faces $Y_1,Y_2$ inside $F$ together with all faces of $X_H$ other than $F$: every other face $F^{\mathrm{\prime }}$ of $X_H$ is disjoint from $Q$, and it is the region of its frontier by (I0), so $Q$ misses $F^{\mathrm{\prime }}$ and $F^{\mathrm{\prime }}$ is still a component of the complement of the new drawing, while every remaining point of the complement lies in an old face other than $F$ or in $F\setminus Q=Y_1\bigsqcup Y_2$. The new facial frontiers are the old cycle frontiers together with $D_1$ and $D_2$, so (I1) passes, and (I0) passes because each old face is still the region of its frontier and each $Y_i$ is the specified component of ${\mathbb{R}}^2\setminus D_i$ opposite the old adjacent region $W$ by step 4.1, whether or not that component is bounded; an ear with $k\ge 1$ edges contributes $k-1$ new vertices, $k$ new edges and one new face, and $\mathrm{\mid }{D}_1\mathrm{\mid }+\mathrm{\mid }{D}_2\mathrm{\mid }=\mathrm{\mid }{J}_1\mathrm{\mid }+\mathrm{\mid }{J}_2\mathrm{\mid }+2k=\mathrm{\mid }J\mathrm{\mid }+2k$, so the sum of the cycle lengths changes by $2k$ and (I2) passes. Induction over the finitely many ears proves (a) and the invariant (I0), and it also proves $V-E+F=2$ for $2$-connected drawings.

The bipartite bound. Let $G$ be connected, simple and bipartite with $V\ge 3$ and put $f(G)=2V-E$; the claim $E\le 2V-4$ is $f(G)\ge 4$. First suppose $G$ is $2$-connected. By step 5.1 every face has a boundary cycle and each such cycle has even length at least $4$: it is a cycle of a bipartite graph, hence even, and it has at least three distinct vertices, hence at least four. By (I2) of step 5.1 the sum of the facial cycle lengths is $2E$, so $4F\le 2E$; with $V-E+F=2$ this gives $E\le 2V-4$. In general suppose $G$ is connected, has $V\ge 3$ and is not $2$-connected. Then some vertex $v$ has $G-v$ disconnected, and splitting the component vertex sets of $G-v$ into two nonempty groups gives connected bipartite drawn subgraphs $G_1,G_2$ on the two vertex sets $\{v\}\cup C_1$ and $\{v\}\cup C_2$, which share exactly $v$, with strictly fewer vertices than $G$, with $V_1+V_2=V+1$ and $E_1+E_2=E$. Induction on $V$ gives $f(G_i)\ge 3$, because for $V_i=2$ the graph is one edge and $f(G_i)=3$, and for $V_i\ge 3$ the claim $f\ge 4$ is obtained by the same splitting argument applied to $G_i$, whose vertex number is smaller. Hence $f(G)=f(G_1)+f(G_2)-2\ge 4$, that is $E\le 2V-4$. Finally $K_{3,3}$ is connected and bipartite with $V=6$ and $E=9$ by [L5], and $9>8=2\cdot 6-4$, so $K_{3,3}$ has no drawing by simple arcs. This proves (c).

Extension: boundary data. Let $G,G^{\mathrm{\prime }}$ and $\phi$ be as in (d) with a bijection $\beta$ as in (ii). By step 5.1 the frontier $\mathrm{Fr}(F)$ of every face is a cycle of the drawing and, by the invariant (I0) of step 5.1, each face $F$ is the region of its frontier cycle $\mathrm{Fr}(F)$; the same holds in the drawing of $G^{\mathrm{\prime }}$, whose $2$-connected drawing also satisfies (I1) and (I0). By (ii) the isomorphism $\phi$ carries $\mathrm{Fr}(F)$ onto $\mathrm{Fr}(\beta (F))$, and by (ii) the unique outer face is paired with the unique outer face, so a face is bounded exactly when its paired face is bounded; hence for every face $F$ the regions $F$ and $\beta (F)$ are both bounded or both unbounded. Choose for each edge $e$ of $G$ any homeomorphism $e\to \phi (e)$ matching endpoints, which exists since both are embedded arcs, and let $h:X\to X^{\mathrm{\prime }}$ be the resulting map of point sets; it is a homeomorphism, because it is continuous and injective on the finite closed cover by edge closures and its inverse is assembled from the inverse homeomorphisms in the same way, and by construction $h(v)=\phi (v)$ for every vertex and $h$ carries each edge onto the edge of its image. For each face $F$ the restriction $h{\mathrm{\mid }}_{\mathrm{Fr}(F)}$ is a homeomorphism from the Jordan curve $\mathrm{Fr}(F)$ onto the Jordan curve $\mathrm{Fr}(\beta (F))$.

Extension: assembling the homeomorphism. For each face $F$ apply the extension assertion of [F2] to the homeomorphism $h{\mathrm{\mid }}_{\mathrm{Fr}(F)}$ and use that $F$ and $\beta (F)$ are both bounded or both unbounded by step 6.2: there is a homeomorphism ${\mathrm{\Psi }}_F:{\mathbb{R}}^2\to {\mathbb{R}}^2$ with ${\mathrm{\Psi }}_F{\mathrm{\mid }}_{\mathrm{Fr}(F)}=h{\mathrm{\mid }}_{\mathrm{Fr}(F)}$ and ${\mathrm{\Psi }}_F(F)=\beta (F)$, the latter because $F$ is a region of the Jordan curve $\mathrm{Fr}(F)$ and ${\mathrm{\Psi }}_F$ carries the two regions of that curve onto the two regions of $\mathrm{Fr}(\beta (F))$ according to boundedness. Define $\mathrm{\Phi }:{\mathbb{R}}^2\to {\mathbb{R}}^2$ to equal $h$ on the drawing $X$ and to equal ${\mathrm{\Psi }}_F$ on each face $F$. The sets $X$ and the closures $\bar{F}$ are finitely many closed sets covering the plane, and any two of them meet either in $X$ or not at all, so the definitions agree on overlaps and $\mathrm{\Phi }$ is continuous by [L2]; it is injective, because it maps $X$ bijectively onto $X^{\mathrm{\prime }}$ and each face bijectively onto its paired face, and it is surjective for the same reason. Define the actual inverse piecewise to equal $h^{-1}$ on $X^{\mathrm{\prime }}$ and ${\mathrm{\Psi }}_F^{-1}$ on $\beta (F)$ for each $F$. On each paired frontier ${\mathrm{\Psi }}_F^{-1}$ agrees with $h^{-1}$, so the finite closed-cover pasting argument makes this inverse continuous; its compositions with $\mathrm{\Phi }$ are the identity on every face and edge. Thus $\mathrm{\Phi }$ is a homeomorphism of the plane with $\mathrm{\Phi }(v)=\phi (v)$ for every vertex, $\mathrm{\Phi }$ carrying each edge onto its image edge, and $\mathrm{\Phi }(F)=\beta (F)$ for every face, in particular for the designated and outer faces. This proves (d).

Collecting the cases: (a) is step 5.1, (b) is step 3.1 together with the $2$-connected case of step 5.1, (c) is step 6.1 and (d) is step 7.1. Degenerate cases: a graph with one vertex and no edges has $V-E+F=1-0+1=2$ when connected, is not $2$-connected, so (a) and the $2$-connected part of (c) are vacuous there, (b) is the general formula of step 3.1, and (d) concerns $2$-connected graphs, which have at least three vertices; the empty graph has $V=E=c=0$ and $F=1$, treated in step 3.1. Choice enters exactly as declared in [A1], through Jordan separation, the Jordan-Schonflies extension, Alexander duality and the universal coefficient theorem; all remaining selections are made from the finitely many edges, faces and spanning trees of the finite data.