Exact routing for micro-electrode-dot-array digital microfluidic biochips

Digital microfluidics is an emerging technology that provide fluidic-handling capabilities on a chip. One of the most important issues to be considered when conducting experiments on the corresponding biochips is the routing of droplets. A recent variant of biochips uses a micro-electrode-dot-array (MEDA) which yields a finer controllability of the droplets. Although this new technology allows for more advanced routing possibilities, it also poses new challenges to corresponding CAD methods. In contrast to conventional microfluidic biochips, droplets on MEDA biochips may move diagonally on the grid and are not bound to have the same shape during the entire experiment. In this work, we present an exact routing method that copes with these challenges while, at the same time, guarantees to find the minimal solution with respect to completion time. For the first time, this allows for evaluating the benefits of MEDA biochips compared to their conventional counterparts as well as a quality assessment of previously proposed routing methods in this domain.