Minimal obstructions for 1-immersions and hardness of 1-planarity testing

Vladimir P. Korzhik; Bojan Mohar

Source-linked AI summary

Minimal obstructions for 1-immersions and hardness of 1-planarity testing

Vladimir P. Korzhik, Bojan Mohar

arXiv:1110.4881v1Oct 21, 2011math.CO

TL;DR

The paper addresses limited knowledge about recognizing 1-planar graphs and about how many minimal non-1-planar graphs exist and whether they can be characterized. The paper constructs two explicit infinite families of MN-graphs with minimum degree at least three, describes PN-graphs, and reduces 3-colorability of planar graphs to 1-planarity testing. For every n ≥ 63, there are at least 2^((n−54)/4) nonisomorphic minimal non-1-planar graphs of order n, and 1-planarity testing is NP-complete.

Problem
The paper addresses limited knowledge about recognizing 1-planar graphs and about how many minimal non-1-planar graphs exist and whether they can be characterized.
Source: §1 · p. 3
Method
The paper constructs two explicit infinite families of MN-graphs with minimum degree at least three, describes PN-graphs, and reduces 3-colorability of planar graphs to 1-planarity testing.
Source: §1 · pp. 4–5
Results
For every n ≥ 63, there are at least 2^((n−54)/4) nonisomorphic minimal non-1-planar graphs of order n, and 1-planarity testing is NP-complete.
Source: §1 · p. 5
Takeaways & Limitations
PN-graphs support constructions of graphs with desired properties, including 1-planar graphs with exactly k > 0 different plane 1-immersions and MN-graphs.
Source: §1 · p. 5
For a similar proof on simple graphs, the needed graphs with a unique plane k-immersion for k ≥ 2 are nontrivial to construct and do not readily follow from the U-graph construction.
Source: §6 · p. 53

Abstract

from arXiv · show

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non-1-planar graph $G$ is minimal if the graph $G-e$ is 1-planar for every edge $e$ of $G$. We construct two infinite families of minimal non-1-planar graphs and show that for every integer $n > 62$, there are at least $2^{(n-54)/4}$ nonisomorphic minimal non-1-planar graphs of order $n$. It is also proved that testing 1-planarity is NP-complete.

1 Introduction

Earlier constructions established infinitely many minimal non-1-planar graphs but gave few explicit examples; this paper develops two explicit families and approaches to proving non-1-planarity. It also addresses recognition complexity, which was not known to have a polynomial-time solution.

1 Introduction

The K3,3-based family replaces six edges with special subgraphs and has minimum degree at least three.Its minimality is easy to verify, while proving non-1-planarity requires long, delicate arguments.Source: §1 · p. 4
For every n ≥ 63, there are at least 2^((n−54)/4) nonisomorphic minimal non-1-planar graphs of order n.The paper establishes this bound using the constructed MN-graphs.Source: §1 · p. 5
PN-graphs are 3-connected planar graphs whose only plane 1-immersion is their plane embedding; that fixed embedding can prevent an extension from being 1-immersed.The paper uses PN-graphs as subgraphs in another construction of MN-graphs.Source: §1 · p. 5
PN-graph constructions also yield 1-planar graphs with exactly k > 0 different plane 1-immersions and other graphs with desired properties.The paper identifies MN-graphs among the possible constructions.Source: §1 · p. 5
The paper proves 1-planarity testing NP-complete using a geometric reduction from planar 3-colorability, or alternatively planar 3-satisfiability.The reduction addresses the recognition problem for which a polynomial-time algorithm was unclear.Source: §1 · pp. 3, 5
The proof of Theorem 5 can be modified to show that k-planarity testing for multigraphs is NP-complete.The paper treats this extension in its final section.Source: §1 · p. 5

2 Chain graphs based on K3,3

The section defines chain graphs by replacing six edges of K₃,₃ with A- and B-chains and proves that every chain graph is minimal non-1-planar. It uses these graphs to establish that, for every n ≥ 63, there are at least 2^((n−54)/4) nonisomorphic minimal non-1-planar graphs of order n.

2 Chain graphs based on K3,3

A chain graph is formed from K3,3 by replacing three edges at one vertex with A-chains and three edges at another same-chromatic-class vertex with B-chains, each of length at least 2.The three vertices adjacent to Ω are the base vertices.Source: §2 · pp. 6, 8
In a minimum-crossing 1-immersion, no two edges within an A- or B-chain link cross.The proof eliminates possible crossings by redrawing within a disk or moving a trivalent vertex, contradicting minimality of the crossing count.Source: §2 · pp. 9–10
For any 3-cycle of one chain, all core vertices of a nonadjacent opposite-type chain lie on the same side, with at most one vertex of that chain on the other side; consequently, nonadjacent chains do not cross.These constraints apply to 1-immersions with a minimum number of crossings.Source: §2 · pp. 10, 12
For every chain graph G and edge e, deleting e yields a 1-planar graph; if e is an Ω-edge, the result is planar; otherwise, the proof constructs a 1-immersion.For the middle edge of a B-link, the corresponding B-chain can be crossed by an A-chain.Source: §2 · pp. 8–9
At least one chain must contain a link whose every end-to-end path is crossed by an Ω-edge; otherwise the paths and Ω-edges yield an embeddable K3,3 subdivision, a contradiction.The proof uses the absence of crossings between nonadjacent chains and removes crossings between adjacent paths to obtain the contradiction.Source: §2 · pp. 12, 14
For every n ≥ 63, there are at least 2^((n−54)/4) nonisomorphic minimal non-1-planar graphs of order n.The theorem follows because every chain graph is a minimal non-1-planar graph.Source: §2 · p. 17
A chain graph with A-chain lengths 2, 2, ℓ and B-chain lengths 2, 3, t has order 35 + 3ℓ + 4t, where ℓ ≥ 2 and t ≥ 4.For every n ≥ 63, ℓ can be chosen from 2 through 5 so that n = 35 + 3ℓ + 4t.Source: §2 · p. 17
Applying the Fig. 2(e) modification to links in the two B-chains of length at least 3 yields 2t−1 nonisomorphic chain graphs of that order.The theorem uses this family construction to obtain its lower bound for each n ≥ 63.Source: §2 · p. 17

3 PN-graphs

This section develops conditions under which a 3-connected planar graph has no proper 1-immersion and constructs graphs satisfying many of them. It establishes that the constructed graphs and a second extension are PN-graphs, using cycles in H to obtain four edge-disjoint paths in G in support of condition (C7).

Theorem 3

Every 3-connected planar graph satisfying conditions C1–C9 has no proper 1-immersion.Such graphs are PN-graphs by definition; the section denotes their class by A.Source: §3 · pp. 19, 25

Theorem 3 proof

In ϕ, a 3-cycle has vertices both inside and outside; for any such cycle C, there is only one vertex inside C or outside C, and that vertex belongs to N(C).Source: §3 · pp. 19–20
If an edge belongs to two 3-cycles, both its endpoints have degree at least 5.Source: §3 · p. 21

Examples in A

The section gives two infinite families of graphs in A, one of which is used in Section 4 to construct MN-graphs.Source: §3 · p. 25

Medial extensions

Every medial extension of a graph in H is 3-connected and planar, and satisfies conditions C1–C6 and C8.The construction places a vertex on each edge of H, forms triangles at 3-valent vertices, and adds a diagonal to each 4-cycle associated with a 4-valent vertex.Source: §3 · p. 26

Checking condition C7

To check condition C7 for a medial extension, the method subdivides every edge of H and considers paths associated with paths in the subdivided graph.Source: §3 · p. 27

3 PN-graphs

If H has a cycle through two 2-valent vertices, G has four edge-disjoint paths connecting those vertices.Source: §3 · p. 28
For every n ≥ 6, the constructed medial extension Gn of P3 × Cn is a PN-graph.The proof verifies conditions (C1)–(C9).Source: §3 · pp. 28, 30
For Gn, symmetry reduces the (C7) check to two 3-cycle cases, where 2-connected components and explicit paths establish four C-independent edge-disjoint connections.The proof handles vertices in the remaining components using paths associated with H and separately exhibits paths for the exceptional vertices.Source: §3 · pp. 28–30
A second extension G′n satisfies (C1)–(C6) and (C8), while its lack of 4-cycles gives (C9).Source: §3 · p. 30
For G′n, symmetry and deletion leave a 2-connected component whose vertices are connected by four C-independent edge-disjoint paths, establishing (C7) and PN status.Source: §3 · pp. 30–31

4 MN-graphs based on PN-graphs

The section constructs minimal non-1-planar graphs from PN-graphs and proves the constructed family is non-1-planar while deleting any edge makes it 1-planar. Its method uses the unique plane embedding of a PN-graph to constrain where the remaining graph can be immersed.

4 MN-graphs based on PN-graphs

Sm(λ) is formed from Sm by replacing selected edges around each central vertex and deleting the 2-valent vertices of its central paths.Its cycles B0 through Bm−3 have length 12m−2, while Bm−2, Bm−1, and Bm have length 12m−2+n.Source: §4 · pp. 31, 34
Deleting an edge of a central path lets the remaining central paths lie inside B0; other edge deletions permit a central path to be drawn outside B0.In each case the construction supplies a 1-immersion after deletion.Source: §4 · p. 32
The constructed Sm(λ) is a PN-graph, whose unique plane 1-immersion is used to constrain any proposed immersion of the larger graph.The proof places a PN subgraph inside the cycle Bm−2 and derives a contradiction from the resulting immersion of Jm−2.Source: §4 · pp. 34–35
The non-1-planarity proof bounds how many crossings a central path can have, then uses bypassed vertices and path types to force a contradiction.If sufficiently many central paths bypass a vertex, one must have type at least their number; the maximal-type path argument contradicts this.Source: §4 · pp. 36, 39, 40
For every m ≥4 and λ ∈Φm(n), Sm(λ) is non-1-planar, while deleting any edge makes it 1-planar.Together these properties make each Sm(λ) a minimal non-1-planar graph.Source: §4 · pp. 32, 39
Sm(λ) has order (5m −1)(12m −2) + 5n, and graphs with different m or, at fixed m, different n are nonisomorphic.The passage also states that each such graph is an MN-graph.Source: §4 · p. 40

5 Testing 1-immersibility is hard

The paper proves that deciding whether a graph is 1-immersible is NP-complete. It reduces planar graph 3-colorability to 1-immersibility by constructing uniquely immersed gadgets whose path configurations encode colors.

5 Testing 1-immersibility is hard

Deciding whether a given input graph is 1-immersible is NP-complete.The proof establishes membership in NP and gives a reduction from planar 3-colorability with maximum degree at most four.Source: §5 · p. 41
The reduction constructs, in polynomial time, a graph that is 1-immersible if and only if the input plane graph is 3-colorable.It uses uniquely 1-immersed building blocks connected into a graph that also has a unique 1-immersion, then adds paths.Source: §5 · pp. 41, 45
A 1-immersion assigns each input vertex the color of its activated family, and adjacent vertices receive different colors.Conversely, a proper 3-coloring determines which family is activated at each vertex-block and yields a 1-immersion.Source: §5 · pp. 51–52

6 k-planarity testing for multigraphs

The section sketches a reduction showing that k-planarity testing for multigraphs is NP-complete for k ≥ 2. Replacing each edge by k parallel edges preserves the relevant immersion behavior, linking k-planarity to 1-planarity and proper 3-colorability.

6 k-planarity testing for multigraphs

G(1)(k) has a unique plane k-immersion, obtained by replacing every edge in G(1)'s unique plane 1-immersion with k parallel edges.The proof considers an arbitrary plane k-immersion and shows it must equal this constructed immersion.Source: §6 · p. 52
When two edges cross, every edge in one parallel-edge bundle must intersect every edge in the other bundle.The proof argues by contradiction using the 2-cell bounded by edges in a bundle and the resulting bound on crossings.Source: §6 · pp. 52–53
Replacing each edge by k parallel edges preserves the immersion behavior, yielding NP-completeness of k-planarity testing for multigraphs when k ≥ 2.The construction gives G a plane 1-immersion if and only if G(k) has a plane k-immersion; the paper notes the proof is sketched.Source: §6 · pp. 52–53
For simple graphs, an analogous proof for k ≥ 2 requires graphs with a unique plane k-immersion, whose construction is nontrivial and does not readily follow from U-graphs.Source: §6 · p. 53