pith. sign in

arxiv: 1907.09817 · v1 · pith:MXUOK4QXnew · submitted 2019-07-23 · 🧮 math.CO

Non-separating Planar Graphs

Hooman R. Dehkordi , Graham Farr This is my paper

Pith reviewed 2026-05-24 17:38 UTC · model grok-4.3

classification 🧮 math.CO
keywords non-separating planar graphsforbidden minorsminor-closed classesouterplanar graphswheel graphstriangular prismlinkless graphsplanar embeddings
0
0 comments X

The pith

A graph is non-separating planar exactly when it avoids K1 ∪ K4, K1 ∪ K2,3 and K1,1,3 as minors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that non-separating planar graphs are defined exactly by the absence of three specific minors. A non-separating planar graph admits a crossing-free plane drawing in which every cycle has all remaining vertices on one side. This places the class strictly between outerplanar graphs and general planar graphs. The characterization is then applied to construct maximal linkless graphs that achieve 3n-3 edges.

Core claim

A graph G is a non-separating planar graph if and only if it does not contain K1 ∪ K4 or K1 ∪ K2,3 or K1,1,3 as a minor. Any maximal non-separating planar graph is either an outerplanar graph, a subgraph of a wheel, or obtained by subdividing some side-edges of the 1-skeleton of a triangular prism.

What carries the argument

The three forbidden minors K1 ∪ K4, K1 ∪ K2,3 and K1,1,3 that together characterize the minor-closed class of non-separating planar graphs.

If this is right

  • Non-separating planar graphs are closed under minors and therefore have a finite forbidden-minor list.
  • The class properly contains all outerplanar graphs and is properly contained in the planar graphs.
  • Maximal members of the class have one of three explicit structural descriptions.
  • The class supplies maximal linkless graphs on exactly 3n-3 edges.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The explicit minor list supplies a direct certificate for non-membership that can be checked by standard minor-testing routines.
  • The structural forms for maximal members allow exhaustive construction of all members up to any given order.
  • The linkless-graph application indicates that the same minor obstructions may bound edge counts or other parameters in related spatial embedding problems.

Load-bearing premise

The class of non-separating planar graphs is closed under taking minors.

What would settle it

A single graph that contains none of the three listed minors yet admits no non-separating planar drawing, or a graph that contains one of the minors yet still admits such a drawing.

Figures

Figures reproduced from arXiv: 1907.09817 by Graham Farr, Hooman R. Dehkordi.

Figure 1
Figure 1. Figure 1: Three examples of non-separating planar graphs A set S of graphs is a minor-closed set or minor-closed family of graphs if any minor of a graph G ∈ S is also a member of S. In this paper we characterise non-separating planar graphs. Non-separating planar graphs are a subclass of planar graphs and a superclass of outerplanar graphs and are closed under minors. To characterise non-separating planar graphs we… view at source ↗
Figure 2
Figure 2. Figure 2: Excluded minors for non-separating planar graphs An edge e = (u, v) in a graph G is subdivided by replacing it with two edges (u, w),(w, v) where w is not a vertex of G. A subdivision of a graph G is a graph that can be obtained by some sequence of subdivisions, starting with G. A graph is a triangular prism if it is isomorphic to the graph that is depicted in Figure 3a. A graph is an elongated triangular … view at source ↗
Figure 3
Figure 3. Figure 3: Triangular prism and elongated triangular prism [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A link is composed of two cycles in three dimensions that cannot be separated from each other. certain pairs of points that represent the edges between corresponding vertex pairs of the graph, such that these curves do not intersect and also do not pass through the points that represent the vertices of the graph. Informally, realisations of graphs are drawings of graphs in R3 . Two vertex-disjoint cycles C… view at source ↗
Figure 5
Figure 5. Figure 5: The Petersen family of graphs on the projective plane. (These drawings are drawn based on the drawings in [7].) Robertson, Seymour and Thomas proved that G is linklessly embeddable in R3 if and only it does not contain any graph in the Petersen family as a minor [13, 11]. Among the other characterisations of graphs in terms of forbidden minors, we point out the following famous results: • characterisation … view at source ↗
Figure 6
Figure 6. Figure 6: K1,1,3 Proof. Suppose that such a terminal path P has a chord e. Then it is easy to find a K1,1,3 minor in the graph. A vertex w of a uv-path P is an inner vertex of P if w 6= u and w 6= v. An edge e of a path P is an inner edge of P if e is incident with two inner vertices of P. Given a set P of paths in a graph G, define a middle path P ∈ P to be a path such that for any other path P 0 ∈ P there is an ed… view at source ↗
Figure 7
Figure 7. Figure 7: P2 is the only middle path among the four paths P1, P2, P3, P4, where P1, P2, P3 are uv-paths and P4 is a u 0 v 0 -path. Any graph G that contains a K2,3-subdivision is middle-less if there is no middle path among the terminal paths of any of the spanning K2,3-subdivisions in G. Any graph G with a spanning K2,3-subdivision is middle-ful if it is not middle-less. We divide the rest of lemmas in this section… view at source ↗
Figure 8
Figure 8. Figure 8: Any graph with a W4 minor is middle-ful. Let U be a subset of the vertices of a graph G, then G[U] denotes the subgraph of G induced by U. Similarly, for any subgraph H of the graph G, G[H] denotes the subgraph of G that is induced by the vertices of H. Lemma 3. Let P1, P2, P3 be the terminal paths in a spanning K2,3-subdivision S of a middle-less graph G with no K1,1,3-minor or (K1 ∪ K2,3)-minor where G[P… view at source ↗
Figure 9
Figure 9. Figure 9: u, v, u1, v1 in G Now we show that there is at most one edge in G1 that is not an edge of P1 or P2. To reach a contradiction suppose that G1 has two edges e1 = (u1, v1) and e2 = (u2, v2) that are not among the edges of P1 or P2 (note that it is possible that either u1 = u2 or v1 = v2 or u1 = v2 or v1 = u2) [PITH_FULL_IMAGE:figures/full_fig_p007_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: e1, e2, P1, P2 and P3 in G Choose P to be either P1 or P2 so that the endpoints of e1 and e2 on the other path are distinct. Let G− be the graph that is obtained by contracting all the edges of P except the ones that are incident to the terminal vertices of S into a single vertex w. It is easy to see that there is a W4-minor in G− (see, e.g., [PITH_FULL_IMAGE:figures/full_fig_p008_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Finding a middle path in G− [PITH_FULL_IMAGE:figures/full_fig_p008_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: e 0 , P1, P2, P3, P0 1 and P 00 1 in G. Compare the colouring scheme of Figure 12b with Figure 20a to see how K1 ∪ K2,3 is a minor of G. u 0 v 0 P1 P2 P3 e 0 (a) e 0 , P1, P2 and P3 in G u 0 v 0 P 00 1 P2 P3 e 0 u v P 0 1 (b) P 0 1 and P 00 1 in G [PITH_FULL_IMAGE:figures/full_fig_p009_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: e 0 , P1, P2, P3, P0 1 and P 00 1 in G. (see, e.g., Figure 13b). Then, since the lengths of P1 and P2 are greater than 2, it is easy to see that there is a K2,3 minor in P 0 1 ∪e 0 ∪P2 ∪P3 and an inner vertex v 00 on P 00 1 such that P 0 1 ∪ e 0 ∪ P2 ∪ P3 and v 00 form a K1 ∪ K2,3 minor in G (see, e.g., [PITH_FULL_IMAGE:figures/full_fig_p009_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Finding a K1 ∪ K2,3-minor in G (compare with Figure 12c) [PITH_FULL_IMAGE:figures/full_fig_p009_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Three types of middle-less non-separating planar graphs Proof. Let P1, P2, P3 be the terminal paths and u, v be the terminal vertices in a K2,3-subdivision S of a graph G ∈ G. Since G does not contain K1 ∪ K2,3 as a minor, S is a spanning K2,3-subdivision of G. If G does not have any edges other than the edges of P1, P2, P3 then, clearly, G can be obtained by subdividing the red dashed edges of the graph … view at source ↗
Figure 16
Figure 16. Figure 16: If P1 and P2 are middle paths then G contains K1,1,3 as a minor. The colour scheme used here to colour the vertices of a K1,1,3 minor is the same as the one used in [PITH_FULL_IMAGE:figures/full_fig_p011_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: K1 ∪ K4 Lemma 7. Let P1, P2, P3 be the terminal paths in a spanning K2,3-subdivision S of a graph G with no (K1 ∪ K4)-minor, where P2 is a middle path. Then there is no pair of edges e1 = (u1, v1) and e2 = (u1, v2) in G such that u1 is an inner vertex of P1 or P3 and v1 and v2 are two distinct inner vertices of P2. Proof. To reach a contradiction suppose that there is an edge e1 = (u1, v1) and an edge e2 … view at source ↗
Figure 18
Figure 18. Figure 18: G contains K1 ∪ K4 as a minor. Proof. Let G1 = G[P1 ∪ P2] and G2 = G[P2 ∪ P3]. First we show that G1 and G2 are subgraphs of fan graphs. To reach a contradiction suppose that either G1 or G2 is not a subgraph of a fan graph. Without loss of generality, suppose that G1 is not a subgraph of a fan graph. Since G1 is not a subgraph of a fan graph, there are two edges e1 = (u1, v1) and e2 = (u2, v2) in G1 that… view at source ↗
Figure 19
Figure 19. Figure 19: a). Since P2 is a middle path, there are two edges e1 = (u1, x1) and e2 = (u2, x2) such that u1 is an inner vertex of P1 and u2 is an inner vertex of P3. Since G1 is a subgraph of a fan graph G + 1 with handle h1 we have x1 = h1 and since G2 is a subgraph of fan graph G + 2 with handle h2 we have x2 = h2 (see, e.g., Figure 19b). Let P 0 1 be the part of P1 from u to u1 and let P 0 3 be the part of P3 from… view at source ↗
Figure 20
Figure 20. Figure 20: Finding K1 ∪ K2,3 minor in G [PITH_FULL_IMAGE:figures/full_fig_p013_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: Finding K1 ∪ K2,3 in G are the terminal vertices and P1, P2, P3 are the terminal paths in a spanning K2,3- subdivision S of a graph G with no K1,1,3-minor, no (K1∪K4)-minor, no (K1∪K2,3)- minor, and in which P2 is a middle path. Then there is exactly one edge e 0 = (h1, v0 ) in G1 that is not in P1 ∪ P2 and there is exactly one edge e 00 = (h2, v00) in G2 that is not in P2 ∪ P3, where: • h1 and v 0 are ou… view at source ↗
Figure 22
Figure 22. Figure 22: Finding a K1 ∪ K2,3 minor in G [PITH_FULL_IMAGE:figures/full_fig_p014_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: A separating cycle in a cross section of a link with a plane Case 3b. Graph G is middle-ful. By Lemma 11, G is either a subgraph of a wheel or it is an elongated triangular prism. 4.1. Proof of Theorem 1. Now we are ready to prove Theorem 1. Proof. It is straightforward to verify that in any planar drawing of a graph that contains K1 ∪ K4 or K1 ∪ K2,3 or K1,1,3 as a minor, there are two vertices that are … view at source ↗
read the original abstract

A graph $G$ is a non-separating planar graph if there is a drawing $D$ of $G$ on the plane such that (1) no two edges cross each other in $D$ and (2) for any cycle $C$ in $D$, any two vertices not in $C$ are on the same side of $C$ in $D$. Non-separating planar graphs are closed under taking minors and are a subclass of planar graphs and a superclass of outerplanar graphs. In this paper, we show that a graph is a non-separating planar graph if and only if it does not contain $K_1 \cup K_4$ or $K_1 \cup K_{2,3}$ or $K_{1,1,3}$ as a minor. Furthermore, we provide a structural characterisation of this class of graphs. More specifically, we show that any maximal non-separating planar graph is either an outerplanar graph or a subgraph of a wheel or it can be obtained by subdividing some of the side-edges of the 1-skeleton of a triangular prism (two disjoint triangles linked by a perfect matching). Lastly, to demonstrate an application of non-separating planar graphs, we use the characterisation of non-separating planar graphs to prove that there are maximal linkless graphs with $3n-3$ edges which provides an answer to a question asked by Horst Sachs about the number of edges of linkless graphs in 1983.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper defines a graph G to be non-separating planar if it admits a plane drawing in which every cycle has all remaining vertices on one side. It states that the class is minor-closed, lies strictly between outerplanar graphs and planar graphs, and proves that membership is equivalent to the absence of K1 ∪ K4, K1 ∪ K2,3 and K1,1,3 as minors. It further supplies a structural description of the maximal members of the class (outerplanar, subgraphs of wheels, or subdivisions of the 1-skeleton of the triangular prism) and applies the characterization to exhibit maximal linkless graphs on 3n−3 edges.

Significance. If the central claims hold, the work supplies a clean forbidden-minor theorem for a natural minor-closed subclass of planar graphs together with an explicit structural description of its maximal elements and a concrete application resolving a 1983 question of Sachs on linkless graphs. The combination of a minor characterization, a structural theorem, and an extremal application is a standard and useful contribution in structural graph theory.

major comments (2)
  1. [Abstract and §1] Abstract and §1 (preliminary facts): the statement that non-separating planar graphs are closed under minors is asserted prior to the main theorem. Because the right-hand side of the claimed equivalence is minor-closed by construction, this closure property is load-bearing. A self-contained argument is required showing that if G admits a qualifying drawing then so do all minors of G; in particular, the effect of contraction on the side-of-cycle condition must be verified explicitly.
  2. [Theorem 1] Theorem 1 (forbidden-minor characterization): the proof must establish both directions. The “only if” direction follows once closure under minors is shown and the three listed graphs are verified to violate the drawing condition; the “if” direction requires an argument that every graph avoiding the three minors admits a qualifying drawing. The manuscript should indicate where each direction is proved and whether the structural characterization in the subsequent section is used as an intermediate step.
minor comments (2)
  1. Notation: the symbol K1,1,3 is non-standard; a brief definition or reference to the precise graph (a star K1,3 with one additional pendant edge on a leaf) would aid readability.
  2. The application section on linkless graphs should state explicitly which property of non-separating planar graphs is used to construct the 3n−3 edge examples.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful report and for identifying points where the logical structure and self-contained nature of the arguments can be improved. We will revise the manuscript to provide the requested explicit arguments and clarifications while preserving the original results.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1 (preliminary facts): the statement that non-separating planar graphs are closed under minors is asserted prior to the main theorem. Because the right-hand side of the claimed equivalence is minor-closed by construction, this closure property is load-bearing. A self-contained argument is required showing that if G admits a qualifying drawing then so do all minors of G; in particular, the effect of contraction on the side-of-cycle condition must be verified explicitly.

    Authors: We agree that the closure under minors requires an explicit, self-contained proof before the main theorem, as the referee notes. In the revision we will insert a new lemma (placed in §1 immediately after the definition) that proves preservation under deletion of vertices/edges and under contraction. The contraction case will explicitly track how a cycle C and the vertices on one side map to the contracted graph, verifying that the single-side condition is inherited. revision: yes

  2. Referee: [Theorem 1] Theorem 1 (forbidden-minor characterization): the proof must establish both directions. The “only if” direction follows once closure under minors is shown and the three listed graphs are verified to violate the drawing condition; the “if” direction requires an argument that every graph avoiding the three minors admits a qualifying drawing. The manuscript should indicate where each direction is proved and whether the structural characterization in the subsequent section is used as an intermediate step.

    Authors: We will revise the statement and proof of Theorem 1 to label the two directions explicitly. The 'only if' direction will be proved right after the new closure lemma by checking that each of the three graphs fails the drawing condition. The 'if' direction will be shown to proceed via the structural characterization of maximal members (proved in the following section): any graph avoiding the three minors is contained in a maximal member, which by the structural result admits a qualifying drawing; we will add an outline paragraph at the start of the proof of Theorem 1 making this dependence clear. revision: yes

Circularity Check

0 steps flagged

No circularity: characterization derived directly from drawing definition

full rationale

The paper defines non-separating planar graphs explicitly via existence of a crossing-free drawing in which every cycle has all external vertices on one side. The preliminary statement that the class is minor-closed follows from direct (if non-trivial) construction of suitable drawings on minors and does not rely on the later forbidden-minor theorem. The central iff result is obtained by proving both inclusions separately: graphs satisfying the drawing definition avoid the three listed minors, while graphs avoiding those minors admit such a drawing (via the additional structural characterization into outerplanar graphs, wheel subgraphs, or prism subdivisions). No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation, or definitional renaming; the derivation chain remains self-contained against the given drawing property.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper defines a new graph class but relies entirely on standard background from graph theory; no free parameters, new axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions and closure properties of planar graphs, minors, cycles, and embeddings in the plane.
    Invoked throughout the definition and characterization statements in the abstract.

pith-pipeline@v0.9.0 · 5806 in / 1139 out tokens · 58065 ms · 2026-05-24T17:38:43.619528+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Archdeacon

    D. Archdeacon. A Kuratowski theorem for the projective plane. Journal of Graph Theory , 5(3):243–246, 1981

    work page 1981

  2. [2]

    Archdeacon, C

    D. Archdeacon, C. P. Bonnington, N. Dean, N. Hartsfield, and K. Scott. Obstruction sets for outer-cylindrical graphs. Journal of Graph Theory , 38(1):42–64, 2001

    work page 2001

  3. [3]

    Archdeacon, N

    D. Archdeacon, N. Hartsfield, C. Little, and B. Mohar. Obstruction sets for outer-projective- planar graphs. Ars Combinatoria, 49:113–128, 1998

    work page 1998

  4. [4]

    Chartrand and F

    G. Chartrand and F. Harary. Planar permutation graphs.Annales de l’Institut Henri Poincaré. Probabilités et Statistiques, 3(4):433–438, 1967

    work page 1967

  5. [5]

    J. H. Conway and C. McA. Gordon. Knots and links in spatial graphs.Journal of Graph Theory, 7(4):445–453, 1983

    work page 1983

  6. [6]

    H. R. Dehkordi and G. Farr. A stronger version of the Hanani-Tutte Theorem

    work page

  7. [7]

    Kawarabayashi, S

    K. Kawarabayashi, S. Kreutzer, and B. Mohar. Linkless and flat embeddings in 3-space and the unknot problem. InProceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, pages 97–106. ACM, 2010

    work page 2010

  8. [8]

    Kuratowski

    C. Kuratowski. Sur le problème des courbes gauches en topologie.Fundamenta Mathematicae, 15(1):271–283, 1930

    work page 1930

  9. [9]

    W. Mader. Homomorphiesätze für graphen.Mathematische Annalen, 178(2):154–168, 1968

    work page 1968

  10. [10]

    Myrvold and J

    W. Myrvold and J. Woodcock. A large set of torus obstructions and how they were discovered. The Electronic Journal of Combinatorics , 25(1):1–16, 2018

    work page 2018

  11. [11]

    Robertson, P

    N. Robertson, P. Seymour, and R. Thomas. Sachs’ linkless embedding conjecture.Journal of Combinatorial Theory, Series B , 64(2):185–227, 1995

    work page 1995

  12. [12]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. XX. Wagner’s conjecture.Journal of Combi- natorial Theory, Series B , 92(2):325–357, 2004

    work page 2004

  13. [13]

    Robertson, P

    N. Robertson, P. D. Seymour, and R. Thomas. A survey of linkless embeddings. In N. Robertson and P. D. Seymour, editors,Graph Structure Theory, pages 125–136. American Mathematical Society, 1991

    work page 1991

  14. [14]

    H. Sachs. On a spatial analogue of Kuratowski’s theorem on planar graphs — an open problem. In M. Borowiecki, J. W. Kennedy, and M. M. Sysło, editors,Graph Theory, pages 230–241. Springer, 1983

    work page 1983

  15. [15]

    K. Wagner. Bemerkungen zum Vierfarbenproblem.Jahresbericht der Deutschen Mathematiker- Vereinigung, 46:26–32, 1936

    work page 1936