didericis
41227c6a0f
- Main paper: dual_decomposition_minimal_counterexamples/ -> face_monochromatic_pairs/. Title is now "Face-Monochromatic Pairs and the Four Colour Theorem". - Companion paper: dual_decomposition_iterated_reduction/ -> iterated_reduction_in_reduced_dual/. Title is now "An Iterated Reduction in the Reduced Dual". Its prose and bibliography cite the parent under the new title. - Update one absolute sys.path reference inside check_conj_face_kempe_n15.py that pointed at the old folder. Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
123 lines
4.4 KiB
Python
123 lines
4.4 KiB
Python
"""Draw a 3-panel illustration of cubic-graph edge contraction:
|
|
(1) the original cubic graph fragment with edge e = uv highlighted;
|
|
(2) after deleting e (u, v are degree-2);
|
|
(3) after smoothing u, v (gone, replaced by single edges).
|
|
|
|
Produces fig_cubic_edge_contraction.png.
|
|
"""
|
|
import os
|
|
import matplotlib.pyplot as plt
|
|
from matplotlib.patches import FancyArrowPatch
|
|
|
|
OUT_DIR = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
|
|
|
|
DARK = '#374151'
|
|
GRAY = '#9ca3af'
|
|
HIGHLIGHT = '#dc2626' # the edge being contracted (panel 1)
|
|
GHOST = '#fca5a5' # removed edges (panel 2)
|
|
DEG2 = '#f59e0b' # degree-2 vertices (panel 2)
|
|
NEW = '#2563eb' # smoothed-in new edges (panel 3)
|
|
|
|
|
|
# Positions: u centered at (-1, 0), v at (1, 0); their outer neighbors angled.
|
|
pos = {
|
|
'u': (-1.0, 0.0),
|
|
'v': ( 1.0, 0.0),
|
|
'a': (-2.2, 1.0),
|
|
'b': (-2.2, -1.0),
|
|
'c': ( 2.2, 1.0),
|
|
'd': ( 2.2, -1.0),
|
|
}
|
|
|
|
|
|
def draw_vertex(ax, p, color, size=110, label=None, label_offset=(0, 0.22)):
|
|
ax.scatter([p[0]], [p[1]], s=size, color=color, zorder=4)
|
|
if label is not None:
|
|
ax.text(p[0] + label_offset[0], p[1] + label_offset[1], label,
|
|
ha='center', va='center', fontsize=12, zorder=5,
|
|
color=DARK)
|
|
|
|
|
|
def draw_edge(ax, p, q, color, lw=2.0, ls='-', zorder=2):
|
|
ax.plot([p[0], q[0]], [p[1], q[1]], color=color, lw=lw, ls=ls,
|
|
zorder=zorder, solid_capstyle='round')
|
|
|
|
|
|
def panel_before(ax):
|
|
# Outer edges (gray)
|
|
for (x, y) in [('a', 'u'), ('b', 'u'), ('c', 'v'), ('d', 'v')]:
|
|
draw_edge(ax, pos[x], pos[y], DARK, lw=2.0)
|
|
# The highlighted edge e = uv
|
|
draw_edge(ax, pos['u'], pos['v'], HIGHLIGHT, lw=3.2)
|
|
# Vertices
|
|
for v in ('a', 'b', 'c', 'd'):
|
|
draw_vertex(ax, pos[v], DARK, size=60)
|
|
draw_vertex(ax, pos['u'], DARK, size=120, label='$u$',
|
|
label_offset=(-0.05, 0.28))
|
|
draw_vertex(ax, pos['v'], DARK, size=120, label='$v$',
|
|
label_offset=(0.05, 0.28))
|
|
# Label on the edge
|
|
mid = ((pos['u'][0] + pos['v'][0]) / 2,
|
|
(pos['u'][1] + pos['v'][1]) / 2)
|
|
ax.text(mid[0], mid[1] + 0.25, '$e$', ha='center', va='center',
|
|
fontsize=13, color=HIGHLIGHT, zorder=5)
|
|
ax.set_title('(1) cubic plane graph with edge $e = uv$',
|
|
fontsize=11, color=DARK, pad=8)
|
|
|
|
|
|
def panel_after_delete(ax):
|
|
# Outer edges (gray)
|
|
for (x, y) in [('a', 'u'), ('b', 'u'), ('c', 'v'), ('d', 'v')]:
|
|
draw_edge(ax, pos[x], pos[y], DARK, lw=2.0)
|
|
# Ghost the deleted edge
|
|
draw_edge(ax, pos['u'], pos['v'], GHOST, lw=2.0, ls=':')
|
|
# Vertices: u, v are now degree-2 (highlighted color)
|
|
for v in ('a', 'b', 'c', 'd'):
|
|
draw_vertex(ax, pos[v], DARK, size=60)
|
|
draw_vertex(ax, pos['u'], DEG2, size=140, label='$u$',
|
|
label_offset=(-0.05, 0.32))
|
|
draw_vertex(ax, pos['v'], DEG2, size=140, label='$v$',
|
|
label_offset=(0.05, 0.32))
|
|
ax.set_title('(2) delete $e$: $u, v$ now have degree $2$',
|
|
fontsize=11, color=DARK, pad=8)
|
|
|
|
|
|
def panel_after_smooth(ax):
|
|
# The smoothed-in new edges
|
|
draw_edge(ax, pos['a'], pos['b'], NEW, lw=3.0)
|
|
draw_edge(ax, pos['c'], pos['d'], NEW, lw=3.0)
|
|
# Outer vertices remain
|
|
for v in ('a', 'b', 'c', 'd'):
|
|
draw_vertex(ax, pos[v], DARK, size=60)
|
|
# u, v are gone — show their former positions as faint markers
|
|
ax.scatter([pos['u'][0], pos['v'][0]], [pos['u'][1], pos['v'][1]],
|
|
s=140, facecolors='none', edgecolors=GRAY, lw=1.0,
|
|
linestyles='--', zorder=3)
|
|
ax.text(pos['u'][0], pos['u'][1] + 0.32, '$u$ gone',
|
|
ha='center', va='center', fontsize=9, color=GRAY)
|
|
ax.text(pos['v'][0], pos['v'][1] + 0.32, '$v$ gone',
|
|
ha='center', va='center', fontsize=9, color=GRAY)
|
|
ax.set_title('(3) smooth $u, v$: their incident edges merge',
|
|
fontsize=11, color=DARK, pad=8)
|
|
|
|
|
|
def main():
|
|
fig, axes = plt.subplots(1, 3, figsize=(13.5, 4.2))
|
|
for ax in axes:
|
|
ax.set_xlim(-3.0, 3.0)
|
|
ax.set_ylim(-1.7, 1.7)
|
|
ax.set_aspect('equal')
|
|
ax.axis('off')
|
|
panel_before(axes[0])
|
|
panel_after_delete(axes[1])
|
|
panel_after_smooth(axes[2])
|
|
plt.subplots_adjust(left=0.02, right=0.98, top=0.92, bottom=0.04,
|
|
wspace=0.05)
|
|
out = os.path.join(OUT_DIR, 'fig_cubic_edge_contraction.png')
|
|
plt.savefig(out, dpi=180, bbox_inches='tight')
|
|
print(f"wrote {out}")
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main()
|