






















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 and only if the corresponding great shadow is planar. In this paper, we characterize all graphs with planar great shadows. Such graphs are always bipartite cactus graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。