4
$\begingroup$

A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the proofs themselves are not important to the (already long) paper and I have always been terrible at writing proofs about planar embeddings and related things (so you are sparing any would-be readers as well). Unfortunately I was not able to find references for these specific results and so I thought I would post them here and ask if anyone can provide some references.

If you do not know specific references but perhaps know some short, preferably combinatorial, proofs of these results using results for which you do have references, then that may also be helpful.

I assume that planar embeddings are polygonal, i.e., edges are embedded as finitely many straight line segments. I cannot assume that my graphs are 3-connected. By facial cycle I mean a cycle of the graph which is the boundary of a face in some planar embedding. Below are the results I am looking for references for:

Proposition 1: Suppose $G$ is a planar graph with cycle $C = u_1, \ldots, u_k$. Let $G'$ be the graph obtained from $G$ by adding a new vertex $u$ adjacent to each $u_i$. Then $C$ is a facial cycle of $G$ if and only if $G'$ is planar. Moreover, any planar embedding of $G$ in which $C$ is bounding some face $F$ can be extended to a planar embedding of $G'$ where $u$ is embedded in $F$ and then connected to the vertices $u_1, \ldots, u_k$.

Proposition 2: Let $G$ be a graph and let $S \subseteq V(G)$. Then $G$ has a planar embedding which has a face incident to every vertex of $S$ if and only if the graph $G'$ obtained from $G$ by adding a new vertex $s$ adjacent to every element of $S$ is planar. Moreover, any planar embedding of $G$ in which the vertices of $S$ are incident to a common face $F$ can be extended to a planar embedding of $G'$ where $s$ is embedded in $F$ and then connected to every vertex of $S$.

Proposition 3: Suppose that $G_1$ and $G_2$ are planar graphs with facial cycles $C_1 = u^1_1, \ldots, u^1_\ell$ and $C_2 = u^2_1, \ldots, u^2_k$ respectively. Let $G'$ be the graph obtained from $G_1 \cup G_2$ by adding edges $u^1_1u^2_1, \ldots, u^1_m u^1_m$ for some $m \le \min\{\ell,k\}$. Then $G'$ is planar and $C' = u^1_m,u^1_{m+1}, \ldots, u^1_\ell, u^1_1, u^2_1,u^2_k,u^2_{k-1},\ldots, u^2_m$ is a facial cycle.

Improve this question
$\endgroup$
9
  • $\begingroup$ In Prop 1, first part, you can't ask if $C$ is a facial cycle of $G$ unless $G$ is embedded. It isn't true that $C$ must be a facial cycle in every embedding of $G$, but it seems to be true that $C$ is a facial cycle in some embedding. $\endgroup$
    – Brendan McKay
    Commented Oct 4, 2019 at 3:13
  • $\begingroup$ @BrendanMcKay In the question I defined "facial cycle" to be a cycle that is the boundary of a face in some planar embedding of the graph. But you are probably right that this is not a standard definition. $\endgroup$
    – David Roberson
    Commented Oct 4, 2019 at 8:58
  • $\begingroup$ Thanks, I didn't notice that definition. But you are correct that it isn't standard. As far as I am aware, embedded graphs have facial cycles not graphs in general, though in cases like 3-connected graphs, which have only one embedding, the distinction is not adhered to diligently. $\endgroup$
    – Brendan McKay
    Commented Oct 4, 2019 at 11:31
  • 3
    $\begingroup$ I guess you can simply state these results and say that they are possibly already known and the proofs are straightforward. I would not bother giving references for such basic results. $\endgroup$
    – Joao Costalonga
    Commented Oct 4, 2019 at 15:38
  • 1
    $\begingroup$ Proposition 3 would be easier to read without superscripts: Suppose that $G$ and $H$ are planar graphs with facial cycles $C = u_1, \ldots, u_k$ and $D = v_1, \ldots, v_\ell$... $\endgroup$
    – user44143
    Commented Oct 10, 2019 at 13:46

0

Reset to default

You must log in to answer this question.