Conference Proceedings

Seeing Around Corners: Fast Orthogonal Connector Routing

Kim Marriott, Peter J Stuckey, Michael Wybrow, T Dwyer, H Purchase, A Delaney

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | SPRINGER-VERLAG BERLIN | Published : 2014

Abstract

Orthogonal connectors are used in drawings of many types of network diagrams, especially those representing electrical circuits. One approach for routing such connectors has been to compute an orthogonal visibility graph formed by intersecting vertical and horizontal lines projected from the corners of all obstacles and then use an A* search over this graph. However the search can be slow since many routes are in some sense topologically equivalent. We introduce obstacle-hugging routes which we conjecture provide a canonical representative for a set of topologically equivalent routes. We also introduce a new 1-bend visibility graph that supports computation of these canonical routes. Essenti..

View full abstract

Grants

Awarded by ARC through Discovery


Funding Acknowledgements

We acknowledge the support of the ARC through Discovery Project Grants DP0987168 and DP110101390. We also thank the anonymous reviewers for their very helpful comments.