math-research/papers/level_switching/experiments/counterexample_surface_switch.py

"""Counterexample showing that a surface switch on the edge between a
depth-d face F and a depth-(d-1) face F' can create a new face of depth
d (not d-1) when the depth-0 neighbor of F' lies on only one side of
the shared edge.

14-vertex maximal outerplanar L_k. Outer cycle order:
   u, p1, p2, p3, x, q1, v, b1, b2, b3, w, a1, a2, a3 -> u

Central triangle F = (u, v, w) has depth 2.
F' = (u, v, x) has depth 1 (its depth-0 neighbor is the q1-ear on the
v-side of x; its u-side neighbor A_ux is depth 1).
A_uw = (u, a2, w), A_vw = (v, b2, w) are both depth 1.

Surface switch on uv: flip uv -> wx. New faces are
   A = (u, w, x) and B = (v, w, x).
B inherits the depth-0 q1-ear, so depth(B) = 1.
A's neighbors are A_uw (1), A_ux (1), B (1), so depth(A) = 2 = d. BAD.
"""
import os
import math
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon

OUT_DIR = os.path.join(os.path.dirname(os.path.abspath(__file__)), os.pardir)

OUTER = ['u', 'p1', 'p2', 'p3', 'x', 'q1', 'v',
         'b1', 'b2', 'b3', 'w', 'a1', 'a2', 'a3']
n = len(OUTER)

POS = {}
for i, name in enumerate(OUTER):
    a = math.radians(90 - i * (360 / n))
    POS[name] = (math.cos(a), math.sin(a))

OUTER_EDGES = [(OUTER[i], OUTER[(i + 1) % n]) for i in range(n)]

CHORDS_BEFORE = [
    ('u', 'v'), ('u', 'w'), ('v', 'w'),       # central F = (u,v,w)
    ('u', 'x'), ('v', 'x'),                    # F' = (u,v,x)
    ('u', 'a2'), ('a2', 'w'),                  # A_uw = (u,a2,w)
    ('v', 'b2'), ('b2', 'w'),                  # A_vw = (v,b2,w)
    ('u', 'p2'), ('p2', 'x'),                  # A_ux = (u,p2,x)
]

CHORDS_AFTER = [c for c in CHORDS_BEFORE if set(c) != {'u', 'v'}] + [('w', 'x')]

FACES_BEFORE = [
    ('u', 'v', 'w'),       # F        (depth 2 -- bad)
    ('u', 'v', 'x'),       # F'       (depth 1)
    ('u', 'a2', 'w'),      # A_uw     (depth 1)
    ('v', 'b2', 'w'),      # A_vw     (depth 1)
    ('u', 'p2', 'x'),      # A_ux     (depth 1)
    ('v', 'q1', 'x'),      # A_vx     (depth 0)
    ('u', 'a1', 'a2'),     # depth 0
    ('a2', 'a3', 'w'),     # depth 0
    ('v', 'b1', 'b2'),     # depth 0
    ('b2', 'b3', 'w'),     # depth 0
    ('u', 'p1', 'p2'),     # depth 0
    ('p2', 'p3', 'x'),     # depth 0
]

FACES_AFTER = [
    ('u', 'w', 'x'),       # A        (depth 2 -- still bad!)
    ('v', 'w', 'x'),       # B        (depth 1)
    ('u', 'a2', 'w'),
    ('v', 'b2', 'w'),
    ('u', 'p2', 'x'),
    ('v', 'q1', 'x'),
    ('u', 'a1', 'a2'),
    ('a2', 'a3', 'w'),
    ('v', 'b1', 'b2'),
    ('b2', 'b3', 'w'),
    ('u', 'p1', 'p2'),
    ('p2', 'p3', 'x'),
]


def compute_depths(faces, chords):
    """Compute facial depth for each face using threshold-1 definition."""
    outer_set = {frozenset(e) for e in OUTER_EDGES}

    def face_edges(f):
        return {frozenset((f[0], f[1])), frozenset((f[1], f[2])),
                frozenset((f[0], f[2]))}

    # Build inner-face dual
    D = nx.Graph()
    D.add_nodes_from(range(len(faces)))
    for i, fi in enumerate(faces):
        for j, fj in enumerate(faces):
            if i < j and face_edges(fi) & face_edges(fj):
                D.add_edge(i, j)

    B = [i for i, f in enumerate(faces)
         if len(face_edges(f) & outer_set) >= 1]

    depth = {}
    for i in range(len(faces)):
        if not B:
            depth[i] = float('inf')
            continue
        depth[i] = min(nx.shortest_path_length(D, i, b) for b in B)
    return depth


def draw_panel(ax, faces, chords, depth, title, highlight_edge=None,
               highlight_face=None):
    palette = {0: '#86efac', 1: '#fde68a', 2: '#fca5a5'}
    edge_pal = {0: '#16a34a', 1: '#d97706', 2: '#dc2626'}

    for i, f in enumerate(faces):
        d = depth[i]
        face_color = palette.get(d, '#ddd')
        face_edge = edge_pal.get(d, '#333')
        lw = 1.4
        if highlight_face is not None and i == highlight_face:
            face_edge = '#7c2d12'
            lw = 3.0
        poly = Polygon([POS[v] for v in f], closed=True,
                       facecolor=face_color, edgecolor=face_edge,
                       linewidth=lw, alpha=0.7, zorder=0)
        ax.add_patch(poly)
        cx = sum(POS[v][0] for v in f) / 3
        cy = sum(POS[v][1] for v in f) / 3
        ax.text(cx, cy, str(d), ha='center', va='center', fontsize=11,
                color=edge_pal.get(d, '#333'), fontweight='bold')

    # Draw edges
    all_edges = OUTER_EDGES + list(chords)
    for (a, b) in all_edges:
        color = '#333'; lw = 1.2
        if highlight_edge is not None and {a, b} == set(highlight_edge):
            color = '#dc2626'; lw = 3.5
        elif (a, b) == ('w', 'x') or (a, b) == ('x', 'w'):
            color = '#16a34a'; lw = 3.0
        ax.plot([POS[a][0], POS[b][0]], [POS[a][1], POS[b][1]],
                color=color, linewidth=lw, zorder=1)

    # Draw vertices
    for name, (x, y) in POS.items():
        ax.scatter([x], [y], s=260, c='#1f2937', edgecolors='black',
                   linewidths=0.8, zorder=2)
        ax.text(x, y, name, ha='center', va='center',
                fontsize=8, color='white', fontweight='bold', zorder=3)

    ax.set_aspect('equal'); ax.axis('off')
    ax.set_xlim(-1.35, 1.35); ax.set_ylim(-1.35, 1.35)
    ax.set_title(title, fontsize=12)


def main():
    depth_before = compute_depths(FACES_BEFORE, CHORDS_BEFORE)
    depth_after = compute_depths(FACES_AFTER, CHORDS_AFTER)

    print("BEFORE:")
    for i, f in enumerate(FACES_BEFORE):
        print(f"  {f} -> depth {depth_before[i]}")
    print("AFTER:")
    for i, f in enumerate(FACES_AFTER):
        print(f"  {f} -> depth {depth_after[i]}")

    fig, axes = plt.subplots(1, 2, figsize=(15, 7.5))
    draw_panel(axes[0], FACES_BEFORE, CHORDS_BEFORE, depth_before,
               r'Before: $F=(u,v,w)$ depth 2, $F\'=(u,v,x)$ depth 1',
               highlight_edge=('u', 'v'), highlight_face=0)
    draw_panel(axes[1], FACES_AFTER, CHORDS_AFTER, depth_after,
               r'After surface switch on $uv$: $A=(u,w,x)$ still depth 2!',
               highlight_face=0)

    fig.tight_layout()
    out = os.path.join(OUT_DIR, 'fig_counterexample_surface_switch.png')
    fig.savefig(out, dpi=180, bbox_inches='tight')
    plt.close(fig)
    print(f'wrote {out}')


if __name__ == '__main__':
    main()