Planarity of Mycielski-like constructions

-
Abstract

For a graph G, we define its great shadow S(G) as a
construction that duplicates each vertex v in G and sets this
duplicated vertex adjacent to v and all neighbors of v. Great graph
shadows arise naturally in the routing of diode-and-switch circuits
for computer keyboards, and are closely related to the Mycielski
operation. These diode-and-switch circuits can be routed on a
single-sided printed-circuit board if thecorresponding great shadow is
planar. In this talk, I characterize all graphs with planar great
shadows. Such graphs are always bipartite cactus graphs.This problem
emerged while routing a circuit board for a piece of real hardware, a
small mechanical keyboard. The keyboard and bare PCBs will be brought
to the talk for the audience to handle.

Description

Discrete Math Seminar
Friday, September 19
10:00am AZ/MST
WXLR 546
 

Speaker

Devansh Vimal
Arizona State University

Location
WXLR 546